CS 285 Notes

Created by Yunhao Cao (Github@ToiletCommander) in Fall 2022 for UC Berkeley CS 285 (Sergey Levine).

Reference Notice: Material highly and mostly derived from Prof Levine's lecture slides, some ideas were borrowed from wikipedia & CS189.

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License

General Introduction to RL (LEC 1)

Supervised ML

Given $D=\{(x_i,y_i)\}$

we will learn to predict $y$ from $x$ .

usually assumes:

i.i.d. data (previous x,y pair does not affect next x, y pair)

known ground truth outputs in the training

Problem:

Cannot adapt if something fails.

Reinforcement Learning:

Data is not i.i.d: previous outputs influence future inputs!

Ground truth answer is not known, only know if we succeeded or failed (but we generally know the reward)

Compared to traditional reinforcement learning,

With DRL(Deep Reinforcement Learning), we can solve complex problems end-to-end!

But there are challenges:

Humans can learn incredibly quickly
1. Deep RLs are usually slow
1. probably because humans can reuse past knowledge

Not clear what the reward function should be

Not clear what the role of prediction should be

Fundamental Theorem of RL(Lec 4)

Notations + Markov Property

We are actually trying to learn a distribution of action $a$ given the observation $o$ , where $\theta$ is the parameter of the distribution policy $\pi$ . we add subscript $t$ to each term to denote the index in the time-serie since we know in RL that actions are usually correlated.

Sometimes instead of $\pi_\theta (a_t|o_t)$ we will see $\pi_\theta(a_t|s_t)$ .

s_t \rightarrow \text{state} \\ \pi_\theta(a_t|s_t) \rightarrow \text{policy (fully observed)} \\ o_t \rightarrow \text{observation} \\ \pi_\theta(a_t|o_t) \rightarrow \text{policy}

Difference - can use observation to infer state, but sometimes (in this example, car in front of the cheetah) the observation does not give enough information to let us infer state.

State is the true configuration of the system and observation is something that results from the state which may or may not be enough to deduce the state

🔥

The state is usually assumed to be an Markovian state

Markov property is very important property ⇒ If you want to change the future you just need to focus on current state and your current action

However, is your future state independent of your past observation? In general, observations do not satisfy Markov property

Many RL algorithms in this course requires Markov property

Side note on notation

RL world (Richard Bellman)	Robotics (Lev Pontryagin)
$s_t$ state	$x_t$ state
$a_t$ action	$u_t$ action
$r(s,a)$ reward	$c(x,u)$ cost $= -r(x,u)$

In general, we want to minimize:

\min_\theta \mathbb{E}_{s_1:T, a_1: T} [\sum_t c(s_t,a_t)]

We can either write the funciton $c$ as $c$ or $r$ , which stands for either (minimize) cost or (maximize) reward

🔥

Notice that we want to maximize the reward (or minimize the cost) under the expectation of the states that we are going to encounter in production / test environment, not training states.

Definition of Markov Chain

M=\{S,T\}

S \rightarrow \text{state space} \\ s \in S \rightarrow \text{state (discrete or continuous)} \\ T \rightarrow \text{transition operator described by } \mathbb{P}(s_{t+1}|s_t)

The transition “operator”?

\text{let } \mu_{t,i} = \mathbb{P}(s_t = i), \\ \text{then $\vec{\mu}_t$ is a vector of probabilities}, \\ \text{let } T_{i,j} = \mathbb{P}(s_{t+1}=i|s_i=j), \\ \text{then } \vec{\mu}_{t+1} = T\vec{\mu}_t

Definition of Markov Decision Process

M = \{S,A,T,r\}

S \rightarrow \text{action space}, \\ s \in S \rightarrow \text{state (discrete or continuous)} \\ A \rightarrow \text{action space}, \\ a \in A \rightarrow \text{action (discrete or continuous)} \\ r: S \times A \rightarrow \mathbb{R} \rightarrow \\

T \rightarrow \text{transitional operator (now a tensor)} \\ \mu_{t,i} = \mathbb{P}(s_t=i), \\ \xi_{t,k} = \mathbb{P}(a_t=k), \\ \text{So } T_{i,j,k} = \mathbb{P}(s_{t+1}=i | s_t=j,a_t=k) \\ \mu_{t+1,i} = \sum_{j,k}T_{i,j,k} \mu_{t,j} \xi_{t,k}

Partially Observed Markov Decision Process

M = \{S,A,O,T,\xi,r\} \\ S \rightarrow \text{state space} \\ s \in S \rightarrow \text{state (discrete or continuous)} \\ A \rightarrow \text{action space} \\ a \in A \rightarrow \text{action (discrete or continuous)} \\ O \rightarrow \text{observation space} \\ o \in O \rightarrow \text{observation (discrete or continuous)} \\ T \rightarrow \text{transition operation} \\ \xi \rightarrow \text{emission probability $\mathbb{P}(o_t|s_t)$} \\ r: S \times A \rightarrow \mathbb{R} \longrightarrow \text{reward function}

Goal of RL (Finite Horizon / Episodic)

\underbrace{p_{\theta}(s_1,a_1,\dots,s_T,a_T)}_{\mathclap{\mathbb{P}_\theta(\tau), \text{where $\tau$ represents sequence of trajectory}}}=\mathbb{P}(s_1)\prod_{t=1}^T \underbrace{\pi_{\theta(a_t|s_t)} \mathbb{P}(s_{t+1}|s_t,a_t)}_{\mathclap{\text{Markov chain on $(s,a)$}}}

So our goal is to maximize the expectation of rewards

\theta^* = \argmax_\theta \mathbb{E}_{\tau \sim p_\theta}[\sum_t r(s_t,a_t)]

Group action and state together to form augmented states

The markov chain can be described using:

\begin{split} \begin{bmatrix} s_{t+1} \\ a_{t+1} \end{bmatrix} = T\begin{bmatrix} s_t \\ a_t \end{bmatrix} \\ \begin{bmatrix} s_{t+k} \\ a_{t+k} \end{bmatrix} = T^k \begin{bmatrix} s_t \\ a_t \end{bmatrix} \end{split}

So now we can modify the goal a bit towards the markov chain.

\begin{split} \theta^* &= \argmax_\theta \mathbb{E}_{\tau \sim p_\theta(\tau)}[\sum_t r(s_t,a_t)] \\ &= \argmax_\theta \sum_{t=1}^T \mathbb{E}_{(s_t,a_t)\sim p_\theta(s_t,a_t)}[r(s_t,a_t)] \end{split}

Goal of RL (Infinite Horizon)

What if $T = \infin$ ? (Infinite horizon)

We need some way to make objective finite
1. Use average award $\theta^* = \argmax_\theta \frac{1}{T}\mathbb{E}{\tau \sim p\theta(\tau)}[\sum_t r(s_t,a_t)]$
1. Use discounts

Q: Does $p(s_t,a_t)$ converge to a stationary distribution as $t \rightarrow \infin$ ?

Ergodic Property: Every state can transition into another state with a non-zero probability.

“Stationary”: The same before and after transition

\underbrace{\mu = T \mu}_{\text{stationary means the state is same and before after transition}}

(T-I)\mu = 0

This means that $\mu$ is an eigenvector of $T$ with eigenvalue of 1 (always exists under some regularity conditions)

\mu = p_\theta(s,a) \rightarrow \text{stationary distribution}

As $t$ goes further and further from infinity, the reward terms starts to get dominated by the stationary distribution (we have almost inifite $\mu$ states and a finite non-stationary action/state pairs

\begin{split} \lim_{T \rightarrow \infin} \theta^* &= \lim_{T \rightarrow \infin} \argmax_\theta \frac{1}{T}\sum_{t=1}^T \mathbb{E}_{(s_t,a_t) \sim p\theta(s_t,a_t)}[r(s_t,a_t)] \\ &= \argmax_{\theta} \mathbb{E}_{(s,a) \sim p_\theta(s,a)}[r(s,a)] \end{split}

Expectations and Stochastic Systems

RL is about maximizing the expectation of rewards. And expectations can be continuous in the parameters of the corresponding distributions even when the function we are taking expectation of is itself highly discontinuous. Because of this property we can use smooth optimization methods like Gradient Descent

📌

Because the distribution of the probability of getting a reward usually has a continuous PDF.

High-level anatomy of reinforcement learning algorithms

Which parts are expensive?

Value Function & Q Function

Remember that RL problems are framed as argmax of expectation of rewards, but how do we actually deal with the expectations?

📌

Write it out recursively!

We can write this expectation out explicitly as a nested expectation (looks like a DP algorithm!)

\mathbb{E}_{\tau \sim p(s_1)}[\sum_{t=1}^T r(s_t,a_t)] = \\ \mathbb{E}_{s_1 \sim p(s_1)}[\mathbb{E}_{a_1 \sim \pi(a_1|s_1)}[r(s_1,a_1)+\mathbb{E}_{s_2 \sim p(s_2|s_1,a_1)}[\mathbb{E}_{a_2 \sim \pi(a_2|s_2)}[r(s_2,a_2)+\cdots|s_2]|s_1,a_1]|s_1]]

❓

Looks like its messy, but what if we have a function that tells us what value inside the

\mathbb{E}_{a_1 \sim \pi(a_1|s_1)}

is? Specifically, its the value of

r(s_1,a_1)+\mathbb{E}_{s_2 \sim p(s_2|s_1,a_1)}[\mathbb{E}{a_2 \sim \pi(a_2|s_2)}[r(s_2,a_2)+\cdots|s_2]|s_1,a_1]

We will define it as our

Q

function

Q(s_1,a_1) = r(s_1,a_1)+\mathbb{E}_{s_2 \sim p(s_2|s_1,a_1)}[\mathbb{E}_{a_2 \sim \pi(a_2|s_2)}[r(s_2,a_2)+\cdots|s_2]|s_1,a_1]

Then our equation is simplified into

\mathbb{E}_{\tau \sim p(s_1)}[\sum_{t=1}^T r(s_t,a_t)] = \\ \mathbb{E}_{s_1 \sim p(s_1)}[\mathbb{E}_{a_1 \sim \pi(a_1|s_1)}[Q(s_1,a_1)|s_1]]

It’s a lot easier to modify the parameter $\theta$ of $\pi_\theta(a_1|s_1)$ if $Q(s_1,a_1)$ is known

Q-Function Definition

Q^{\pi}(s_t,a_t)=\sum_{t'=t}^T \mathbb{E}_{\pi_\theta}[r(s_{t'},a_{t'})|s_t,a_t] \rightarrow \text{total reward from taking $a_t$ in $s_t$}

Value Function Definition

V^{\pi}(s_t)=\sum_{t'=t}^T \mathbb{E}_{\pi_\theta}[r(s_{t'},a_{t'})|s_t] \rightarrow \text{total reward from $s_t$}

V^{\pi}(s_t) = \mathbb{E}_{a_t \sim \pi(a_t|s_t)}[Q^{\pi}(s_t,a_t)]

Now $\mathbb{E}_{s_1}\sim p(s_1)[V^{\pi}(s_1)]$ is the RL objective.

To use those two functions:

If we have policy $\pi$ , and we know $Q^{\pi}(s,a)$ , then we can improve $\pi$ :

\text{set } \pi^{'}(a|s)=1 \text{ if } a = \argmax_a Q^{\pi}(s,a)

(This policy is at least as good as $\pi$ and probably better)

Compute gradient to increase the probability of good actions $a$ if $Q^{\pi}(s,a) > V^{\pi}(s)$ , then $a$ is better than average. Recall that $V^{\pi}(s) = \mathbb{E}[Q^{\pi}(s,a)]$ under $\pi(a|s)$ .

Modify $\pi(a|s)$ to increase the probability of a if $Q^{\pi}(s,a) > V^{\pi}(s)$

Bellman Operator

First defined in fixed Q-Iteration

Information Theory (LEC 14)

Some useful identities:

$p(x)$ - distribution (over observations x)

$H(p(x))= -\mathbb{E}_{x \sim p(x)}[\log p(x)]$ ⇒ entropy (how “broad” p(x) is)

$I(x;y) = D_{KL}(p(x,y)||p(x)p(y)) = \mathbb{E}_{(x,y) \sim p(x,y)}[\log \frac{p(x,y)}{p(x) p(y)}] = H(p(y)) - H(p(y|x))$
1. mutual information between two variables
1. reduction in entropy after knowing $x$
1. See “empowerment” (Polani et al.) for a typical use
  1. $I(s_{t+1}; a_t) = H(s_{t+1}) - H(s_{t+1}|a_t)$
  1. Can be viewed as quantifying “control authority” in an information-theoretic way

Optimal Control and Planning Algorithms

🔥

In Model-based learning, we need some optimal policy extraction steps to be able to extract a policy from a environment.

Model free completely discard the transition dynamics by sampling from the data points

But we often do know the dynamics
1. Games
1. Easily Modeled Systems
1. Simulated Environments

Or we can learn the dynamics
1. System identification (fit unknown parameters of a known model)
1. Learning (fit a general-purpose model to observed transition data)

Knowing the dynamics make things easier

But how do we extract policies from a known dynamics?

Objective of optimal control:

\min_{a_1, \dots, a_T} \mathbb{E}(c(s_1,s_2,\dots,s_T)|a_1,\dots,a_T)

Open-loop Planning

a_1,\dots,a_T = \argmax_{a_1,\dots,a_T} \mathbb{E}[\sum_t r(s_t,a_t)|a_1,\dots,a_T]

This is sub-optimal because we are not considering that later when we have executed some actions ⇒ we may get supplemented with other information.

Stochastic Optimization

Abstracts away optimal control/planning ⇒ just optimizes a function

a_1,\dots,a_T = \argmax_{a_1,\dots,a_T} J(a_1,\dots,a_T) \rightarrow A = \argmax_{A} J(A)

Simplest Method: Guess and Check (”Random Shooting” method)

pick $A_1, \dots, A_N$ from some distribution (e.g. uniform)

Choose $A_i$ based on $\argmax_i J(A_i)$

Cross-Entropy Method (CEM)

Iterative improvement of the “random shooting method”

sample $A_{1}, \dots, A_{N}$ from $p(A)$ (typically start from Gaussian distribution)

Evaluate $J(A_1), \dots, J(A_N)$

Pick the elites $A_{i_1}, \dots, A_{i_M}$ with the highest value ( $M < N$ )

Refit $p(A)$ to the elites $A_{i_1}, \dots, A_{i_M}$

Repeat this process

See also CMA-ES ⇒ CEM with momentum

Very fast if parallelized

Extremely Simple

But very harsh dimensionality limit

Only open-loop planning

Close-loop Planning

Monte-Carlo Tree Search (MCTS)

Discrete Planning can be viewed as a tree search problem but problem is that with vanilla tree search, the complexity is exponential in time steps

So can we restrict the number of searches without expanding the whole tree?

The idea is to stop at depth $x$ and with the state, approximate the outcomes that come after by using a baseline policy.

Whicih path do we search first?

Choose nodes with best reward, but also prefer rarely visited nodes

So the algorithm:

Find a leaf $s_l$ using $\text{TreePolicy}(s_1)$

Evaluate the leaf using $\text{DefaultPolicy}(s_l)$
1. Start from the root and execute every action in the tree to arrive at the leaf / a new leaf(due to randomness)

Update all values in tree between $s_1$ and $s_l$

Repeat this iteration and then choose best action from $s_1$

UCT TreePolicy( $s_t$ )

If $s_t$ not fully expanded, choose new $a_t$ else choose child with best Score ( $s_{t+1}$ )

Score(s_t)=\frac{Q(s_t)}{N(s_t)}+2C\sqrt{\frac{2 \ln N(S_{t-1}}{N(s_t)}}

Browne, Powley, Whitehouse, Lucas, Cowling, Rohlfshagen, Travener, Perez, Samothrakis, Colton. (2012). A Survey of Monte Carlo Tree Search Methods

Shootting Methods vs. Collocation

Shotting method: optimize over actions only
1. Earlier actions have larger effects on the trajectory

Collocation method: Optimize over actions and states, with constraints

Trajectory Optimization

Because this is a trajectory optimization lecture, we will use $x_t$ for state and $u_t$ for action

If we wanna use gradients, it usually helps to use a 2nd order method to optimize via backpropagation!

Linear Case: Linear Quadratic Regularizer (LQR)

Objective:

\min_{u_1,\dots,u_T} c(x_1,u_1)+c(f(x_1,u_1),u_2)+\cdots+c(f(f(\dots)\dots),u_T)

We will assume that

f(x_t,u_t)=F_t\begin{bmatrix} x_t \\ u_t \end{bmatrix} + f_t

c(x_t,u_t)=\frac{1}{2} \begin{bmatrix} x_t &u_t \end{bmatrix} C_t \begin{bmatrix} x_t \\ u_t \end{bmatrix} + \begin{bmatrix} x_t &u_t \end{bmatrix} c_t

Base case: Solve for $u_T$ only

Q(x_T,u_T)=\text{const}+\frac{1}{2}\begin{bmatrix} x_T \\ u_T \end{bmatrix}^{\top} C_T \begin{bmatrix} x_T \\ u_T \end{bmatrix} + \begin{bmatrix} x_T \\ u_T \end{bmatrix}^\top c_T

We can break $C_T$ and $c_T$ into pieces that affects $u$ and affects $x$

(Note that here we assumed $C_{u_T, x_T} = C_{x_T,u_T}^\top$

C_T = \begin{bmatrix} C_{x_T,X_T} &C_{x_T,u_T} \\ C_{u_T,x_T} &C_{u_T,u_T} \end{bmatrix}

c_T = \begin{bmatrix} c_{x_T} \\ c_{u_T} \end{bmatrix}

\nabla_{u_T} Q(x_T,u_T) = C_{u_T,x_T} x_T + C_{u_T,u_T} u_T + c_{u_T}^{\top} = 0 \\ u_T = -C_{u_T,u_T}^{-1}(C_{u_T,x_T}x_T+c_{u_T}) = K_Tx_T+k_T

Subce $u_T$ is fully determined by $x_T$ , we can write our cost function as

\begin{split} V(x_T) &= \text{const} + \frac{1}{2} \begin{bmatrix} x_T \\ K_Tx_T+k_T \end{bmatrix}^{\top} C_T \begin{bmatrix} x_T \\ K_Tx_T+k_T \end{bmatrix} + \begin{bmatrix} x_T \\ K_T x_T + k_T \end{bmatrix}^\top c_T \\ &=\text{const} + \frac{1}{2} x_T^\top V_T x_T + x_T^\top v_T \end{split}

where

V_T = C_{x_T, x_T}+C_{x_T, u_T}K_T + K_T^\top C_{u_T,x_T} + K_T^\top C_{u_T,u_T}K_T \\ v_T = c_{x_T}+C_{x_T,u_T}k_T+K_T^\top C_{u_T} + K_T^\top C_{u_T, u_T}k_T

So what if we solve for $u_{T-1}$ ? ⇒ $u_{T-1}$ affects $x_T$ !

f(x_{T-1},u_{T-1})=x_T = F_{T-1}\begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix} + f_{T-1}

Q(x_{T-1},u_{T-1})=\text{const}+\frac{1}{2}\begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix}^\top C_{T-1} \begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix} + \begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix}^{\top} c_{T-1} + V(f(x_{T-1},u_{T-1}))

V(x_T)=\text{const} + \frac{1}{2} \begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix}^\top F_{T-1}^\top V_T F_{T-1} \begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix} + \begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix}^\top F_{T-1}^\top V_T f_{T-1} + \begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix}^\top F_{T-1}^\top v_T

Combining the two equations

Q(x_{T-1},u_{T-1})=\text{const} + \frac{1}{2}\begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix}^\top Q_{T-1} \begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix} + \begin{bmatrix} x_{T-1} \\ u_{T-1} \end{bmatrix}^\top q_{T-1}

Q_{T-1} = C_{T-1} + F_{T-1}^\top V_T F_{T-1} \\ q_{T-1} = c_{T-1} + F_{T-1}^\top V_T f_{T-1} + F_{T-1}^\top v_T

Now we can derive the derivative

\nabla_{u_{T-1}} Q(x_{T-1}, u_{T-1}) = Q_{u_{T-1},x_{T-1}}x_{T-1} + Q_{u_{T-1},u_{T-1}} u_{T-1} + q_{u_{T-1}}^\top = 0 \\ u_{T-1} = K_{T-1}x_{T-1} + k_{T-1}

Where

K_{T-1} = -Q_{u_{T-1},u_{T-1}}^{-1} Q_{u_{T-1},x_{T-1}} \\ k_{T-1} = -Q_{u_{T-1},u_{T-1}}^{-1} q_{u_{T-1}}

So looks like we can start from the last timestep and do backward recursion!

After doing backward recursion, we can compute our $u_t$ and $x_t$ by forward recursion

LQR for Stochastic and Nonlinear Systems

Stochastic dynamics:

p(x_{t+1}|x_t,u_t) = N(F_t \begin{bmatrix} x_t \\ u_t \end{bmatrix} + f_t, \Sigma_t )

Then just choose actions according to the linear case (since the randomness is symmetric)

Nonlinear case - Differentiable Dynamic Programming (DDP) / Iterative LQR (ILQR)

Can we approximate a nonlinear system as a linear-quadratic system? (nearby)

f(x_t,u_t) \approx f(\hat{x}_t,\hat{u}_t)+\nabla_{x_t,u_t} f(\hat{x}_t,\hat{u}_t)\begin{bmatrix} x_t - \hat{x}_t \\ u_t - \hat{u}_t \end{bmatrix}

c(x_t,u_t) \approx c(\hat{x}_t, \hat{u}_t)+\nabla_{x_t,u_t} c(\hat{x}_t,\hat{x}_t)+\frac{1}{2} \begin{bmatrix} x_t - \hat{x}_t \\ u_t - \hat{x}_t \end{bmatrix}^\top \nabla_{x_t, u_t}^2 c(\hat{x}_t, \hat{u}_t) \begin{bmatrix} x_t - \hat{x}_t \\ u_t - \hat{u}_t \end{bmatrix}

We will denote the change in $x_t, u_t$ as $\delta x_t, \delta u_t$

\bar{f}(\delta x_t, \delta u_t) = F_t \begin{bmatrix} \delta x_t \\ \delta u_t \end{bmatrix}

\bar{c}(\delta x_t, \delta u_t) = \frac{1}{2} \begin{bmatrix} \delta x_t \\ \delta u_t \end{bmatrix}^\top C_t \begin{bmatrix} \delta x_t \\ \delta u_t \end{bmatrix} + \begin{bmatrix} \delta x_t \\ \delta u_t \end{bmatrix}^\top c_t

Where $F_t = \nabla_{x_t,u_t} f(\hat{x}_t, \hat{u}_t)$ , $C_t = \nabla_{x_t,u_t}^2 c(\hat{x}_t, \hat{u}_t)$ , $c_t = \nabla_{x_t,u_t} c(\hat{x}_t, \hat{u}_t)$

Now we can use LQR with dynamics $\bar{f}$ , cost $\bar{c}$ to find $\delta x_t$ and $\delta u_t$

IQLR is basically just an approximation of Neuton’s method for solving the control objective.

But we used a first-order dynamics approximation here, to get Newton’s method, we need to use a second order dynamics approximation (DDP)

🔥

But this may be a bad idea because we are always going to the approximated minima and the approximation is only usable within a short range We can just add a constant

\alpha

term to the

k_t

in the forward pass ⇒ allows us how much we want to control from our starting point (the smaller

\alpha

is the closer we are to the original starting point)

Additional Reading

Mayne, Jacobson. (1970). Differential dynamic programming.
1. Original differential dynamic programming algorithm.

Tassa, Erez, Todorov. (2012). Synthesis and Stabilization of Complex Behaviors through Online Trajectory Optimization.
1. Practical guide for implementing non-linear iterative LQR.

Levine, Abbeel. (2014). Learning Neural Network Policies with Guided Policy Search under Unknown Dynamics.
1. Probabilistic formulation and trust region alternative to deterministic line search.

Types of RL Algorithms

Remember the objective of RL:

\theta^{*} = \argmax_\theta \mathbb{E}_{\tau \sim p_\theta(\tau)}[\sum_t r(s_t,a_t)]

Policy Gradient
1. Directly differentiate the above objective

Value-based
1. Estimate value function or Q-function of the optimal policy (no explicit policy)
1. Then use those functions to prove policy

Actor-critic (A mix between policy gradient and value-based)
1. Estimate value function or Q-function of the current policy, use it to improve policy

Model-based RL
1. Estimate the transition model, and then
  1. Use it for planning (no explicit policy)
  1. Use it to improve a policy
  1. Other variants

Supervised Learning of Behaviors(LEC 2)

Imitation Learning

⚠️

Does it work: NO!!!!

In practice, after a long time of training it actually worked.

“tightrope walker scenerio”: has to follow exact same behavior otherwise the model does not know what to do

Three angles supervised to steer differently! This trick helped a lot

More like in training data we have scenerios to train the machine how to correct its little mistakes.

Instead of being clever about $p_{\pi_\theta}(o_t)$ , let’s be clever about $p_{data}(o_t)$ ⇒ Do DAgger(Data Aggregation)

DAgger (Data Aggregation)

🔥

Addresses “Distributional Drift”, adds on-policy data to the model

Idea: To collect data from $p_{\pi_\theta}(o_t)$ instead of $p_{data}(o_t)$

How: Just run $\pi_\theta(o_t)$ but we need labels $a_t$

train $\pi_\theta(a_t|o_t)$ on human dataset $D = \{o_1,a_1,\dots,o_N,a_N\}$

run $\pi_\theta(a_t|o_t)$ to obtain $D_\pi = \{o_1,\dots,o_M\}$

Ask humans to label $D_\pi$ with actions $a_t$

Aggregate $D \leftarrow D \cup D_\pi$

But:

Lots of the problem is in step 3
1. We as humans have to watch for feedback and then give optimal actions, cannot just watch a state and give output

What if the model does NOT drift?

Need to mimic expert behavior very accurately

Why might we fail the expert?

Non-Markovian Behavior
1. Unnatural for humans to do perfect Markovian actions: Humans more like $\pi_\theta (a_t|o_1, \dots, o_t)$ ⇒ based on previous observations
1. Solve this by adding RNN / LSTM cells to the network (Fig. 1)
  1. May still work poorly (Figure 2)

Multimodal Behavior (Multiple Modes/Peaks in real distribution)
1. If discrete actions, then this is not an issue
  1. But continuous requires exponential discrete bins (for softmax)
1. Solved by
  1. Output mixture of Gaussians
    1. $\pi(a|o)=\sum_i w_i N(\mu_i,\Sigma_i)$
    1. Tradeoffs:
      1. need more output parameters
      1. The ability to model with this in high dimensions is challenging (in theory the number of mixture elements rises exponentially with dimension increase)
  1. Latent variable models
    1. The output is still Gaussian
    1. In addition to inputting an image into NN, we also input a latent variable(may be drawn from a prior distribution) into the model.
      1. Conditional Variational Autoencoders (VAEs)
      1. Normalizing Flow/realNVP
      1. Stein Variational Gradient Descent
    1. Complex to train
  1. Audoregressive discretization
    1. discretizes one dimension at a time using an NN trick ⇒ never incur the exponential cost
    1. Adds a softmax for one dimension, does a discrete sampling (and obtains a dim 1 value), feed the dim 1 value into another NN and softmax layer, do sampling, obtain dim 2 value, so on.
    1. Have to pick bins

Questions:

Does including history info (LSTM/RNN) mitigate causal confusion?
1. My guess is no since history has no correlation with confusion

Can DAgger mitigate causal confusion?
1. My guess is yes since the model will confuse and then this the part of data that the model is confused on will then be manually labeled.

Whats wrong with imitation learning:

Humans need to provide data, which is limited
1. DL works best when data is plentiful

Humans are not good at providing some actions

Humans can learn autonomously, can we do the same on machines?
1. Unlimited data from own experience
1. continuous self-improvement

Analysis of Imitation Learning

Ross et al. “Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning”

We assume:

\begin{split} & c(s,a) = \begin{cases} 0 & \text{if } a = \pi^*(s) \\ 1 & \text{otherwise} \end{cases}\\ & \pi_\theta(a \ne \pi^*(s)|s) \le \epsilon \space \text{for } s \sim p_{train}(s) \quad \leftarrow \text{the model is doing well on training set} \\ & \text{actually enough for } \mathbb{E}_{p_{train}(s)}[\pi_\theta(a \ne \pi^*(s)|s] \le \epsilon \\ \end{split}

then…

with DAgger

p_{train}(s) \rightarrow p_\theta (s) \\ \mathbb{E}[\sum_t c(s_t.a_t)] \le \epsilon T

Without DAgger

\begin{split} &\text{if } p_{train}(s) \ne p_\theta(s): \\ & p_\theta(s_t)= \underbrace{(1-\epsilon)^t}_{\mathclap{\text{probability that we made no mistakes}}} p_{train}(s_t) + (1-(1-\epsilon)^t) p_{mistake}(s_t) \\ \end{split}

We cannot assume anything for $p_{mistake}$

But we can bound the total variation divergence of training and testing

| p_{\theta}(s_t)-p_{train}(s_t)| = \underbrace{(1-(1-\epsilon)^t)|p_{mistake}(s_t)-p_{train}(s_t)|}_{\mathclap{\text{substitute in the above equation in for $p_\theta(s_t)$}}} \le (1-(1-\epsilon)^t) \times 2

Since $(1-\epsilon)^t \ge 1-\epsilon t$ for $\epsilon \in [0,1]$ ,

| p_{\theta}(s_t)-p_{train}(s_t)| \le 2(1-\epsilon t)

So finally

\begin{split} \mathbb{E}_{p_\theta(s_t)}[\sum_t c(s_t,a_t)] &= \sum_t \sum_{s_t} p_\theta (s_t) c_t(s_t) \\ &\le \sum_t \sum_{s_t} p_{train}(s_t) c_t(s_t) + |p_\theta(s_t) - p_{train}(s_t)| c_{max} \\ &\le \sum_t \epsilon + 2 \epsilon t \\ &\le \epsilon T + 2 \epsilon T^2 \\ & \in O(\epsilon T^2) \end{split}

Another way to imitate (Goal Conditional Behavioral Cloning)

After clarification from class:

Sometimes we have bad “demonstrations” that may lead to different end states

Those demonstrations may be close to each other enough that we can train some “shared policy” for each of those different end states (in a sense that most of previous states can be obtained by a shared weight)

During production / test, specify the end state you want to achieve and then we can predict $\pi_\theta(a|s,g)$

“Learning to Reach Goals via Iterated Supervised Learning” - Dibya, Abhishek

Model-Based RL

e.g.

Dyna

Guided Policy Search

Generate samples(run the policy) ⇒

Fit a model of $p(s_{t+1}|s_t,a_t)$ ⇒

Then improve the policy(a few options)

Improving policy:

Just use the model to plan (no policy)
1. Trajectory optimization / optimal control (primarily in continuous spaces)
  1. Backprop to optimize over actions
1. Discrete planning in discrete action spaces
  1. Monte Carlo tree search

Backprop gradients into the policy
1. Requires some tricks to make it work

Use the model to learn a separate value function or Q function
1. Dynamic Programming
1. Generate simulated experience for model-free learner

Value function based algorithms

e.g.

Q-Learning, DQN

Temporal Difference Learning

Fitted Value Iteration

Generate samples(run the policy) ⇒

Fit a model of $V(s)$ or $Q(s,a)$ ⇒

Then improve the policy(set $\pi(s) = \argmax_\theta Q(s,a)$ )

Direct Policy Gradients

e.g.

REINFORCE Natural Policy Gradient

Trust Region Policy Optimization

Generate samples (run the policy) ⇒

Estimate the return

R_\tau = \sum_t r(s_t,a_t)

Improve the policy by

\theta \leftarrow \theta + \alpha \nabla_\theta \mathbb{E}[\sum_t r(s_t,a_t)]

Actor-critic

e.g.

Asynchronous Advantage Actor-Critic (A3C)

Soft actor-critic (SAC)

Generate samples ⇒

Fit a model $V(s)$ or $Q(s,a)$ ⇒

Improve the policy

\theta \leftarrow \theta + \alpha \nabla_\theta \mathbb{E}[\sum_t r(s_t,a_t)]

Tradeoff between algorithms

Sample efficiency

“How many samples for a good policy?”

Most important question: Is the algorithm off-policy?
1. Off policy means being able to improve the policy without generating new samples from that policy
1. On policy means we need to generate new samples even if the policy is changed a little bit

⚠️

We may still want to use a less efficient algorithm because of the other tradeoffs and maybe the price of generating new samples is really cheap.

Stability & Ease of use

Does our policy converge, and if it does, to what?

🔥

Supervised Learning: Almost always Gradient Descent is very likely to converge Reinforcement Learning: Often not Gradient Descent

Value function fitting:
1. Fixed point iteration
1. At best, minimizes error of fit (“Bellman error”)
  1. Not the same as expected reward
1. At worst, doesn’t optimize anything
  1. Many popular DRL value fitting algorithms are not guaranteed to converge to anything in the nonlinear case

Model-based RL
1. Model is not optimized for expected reward
1. Model minimizes error of fit
  1. This will converge
1. No guarantee that better model = better policy

Policy Gradient
1. The only one that performs Gradient Descent / Ascent on the true objective

Different assumptions

Stochastic or deterministic environments?

Continuous or discrete (states and action)?

Episodic(finite $T$ ) or infinite horizon?

Different things are easy or hard in different settings
1. Easier to represent the policy?
1. Easier to represent the model?

Common Assumptions:

Full observability
1. Generally assumed by value function fitting methods
1. Can be mitigated by adding recurrence

Episodic Learning
1. Often assumed by pure policy gradient methods
1. Assumed by some model-based RL methods
1. Although other methods not assumed, tend to work better under this assumption

Continuity or smoothness
1. Assumed by some continuous value function learning methods
1. Often assumed by some model-based RL methods

Model-Free Alogorithms

Policy Gradients

”REINFORCE algorithm”

Remember: Direct gradient descent on RL objective

\begin{split} \theta^* &= \argmax_\theta \underbrace{ \mathbb{E}_{\tau \sim p_\theta(\tau)} [\sum_t r(s_t,a_t)] }_{\mathclap{J(\theta)}} \\ &= \argmax_{\theta} \sum_{t=1}^T \mathbb{E}_{(s_t,a_t) \sim p_\theta(s_t,a_t)}[r(s_t,a_t)] \end{split}

Note: We don’t know anything about the $p(s_1)$ and $p(s_{i+1}|a_i, s_i)$ , but we can approximate it.

\begin{split} J(\theta)&=\mathbb{E}_{\tau \sim p_\theta(\tau)}[\underbrace{\sum_t r(s_t,a_t)}_{\mathclap{\text{denote as }r(\tau)}}] \\ &= \int p_\theta(\tau)r(\tau)d\tau \\ &\approx \frac{1}{N} \sum_i \sum_t \underbrace{r(s_{i,t}, a_{i,t}}_{\mathclap{\text{Reward of time step $t$ in the $i$-th sample}}}) \end{split}

The larger our sample size N is, the more accurate our estimate will be

\nabla_\theta J(\theta)=\int \nabla_\theta p_\theta(\tau)r(\tau) d\tau

We will use a convenient identity to rewrite this equation so that it can be evaluated without knowing the distribution for $p_\theta(\tau)$

p_\theta(\tau)\nabla \log p_\theta(\tau) = p_\theta(\tau) \frac{\nabla_\theta p_\theta(\tau)}{p_\theta(\tau)} = \nabla_\theta p_\theta(\tau)

Using this identity, we can rewrite the equation

\begin{split} \nabla_\theta J(\theta) &= \int \nabla_\theta p_\theta(\tau)r(\tau)d\tau \\ &= \int p_\theta(\tau)\nabla_\theta \log p_\theta(\tau)r(\tau)d\tau \end{split}

Note:

p_\theta(s_1,a_1,\dots,s_T,a_T)=p(s_1)\prod_{t=1}^T \pi_\theta(a_t|s_t) p(s_{t+1}|s_t, a_t) \\ \log p_\theta(s_1,a_1,\dots,s_T,a_T)=\log p(s_1)+ \sum_{t=1}^T \log \pi_\theta(a_t|s_t) + \log p(s_{t+1}|s_t, a_t)

So if we consider the $\nabla_\theta J(\theta)$ , especially the $\nabla_\theta \log p_\theta(\tau)$ , we see that

\begin{split} \nabla_\theta \log p_\theta(\tau) &= \nabla_\theta[\log p(s_1) + \sum_{t=1}^T \log \pi_\theta(a_t|s_t)+\log p(s_{t+1}|s_t,a_t)] \\ &= \nabla_\theta \sum_{t=1}^T \log \pi_\theta(a_t|s_t) \end{split}

So therefore

\begin{split} \nabla_\theta J(\theta)&=\mathbb{E}_{\tau \sim p_\theta(\tau)}[(\sum_{t=1}^T\nabla_\theta \log \pi_\theta(a_t|s_t))(\sum_{t=1}^Tr(s_t,a_t))] \\ &\approx \frac{1}{N}\sum_{i=1}^N(\sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t})(\sum_{t=1}^T r(s_{i,t},a_{i,t})) \end{split}

Improve by

\theta \leftarrow \theta + \alpha\nabla_\theta J(\theta)

”REINFORCE algorithm” on continuous space

e.g. We can represent $p_\theta(a_t|s_t)$ as $N(f_{\text{neural network}}(s_t);\Sigma)$ ⇒

$\nabla_{\theta} \log \pi_\theta(a_t|s_t)=-\frac{1}{2}\Sigma^{-1}(f(s_t)-a_t)\frac{df}{d\theta}$

Sample $\{\tau^i\}$ from $\pi_\theta(a_t|s_t)$ (run it on the robot)

$\nabla_\theta J(\theta) \approx \sum_i(\sum_t \nabla_\theta \log \pi_\theta(a_t^i|s_t^i))(\sum_t r(s_t^i, a_t^i))$

$\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$

Partial Observability

\nabla_\theta J(\theta) \approx \frac{1}{N}\sum_{i=1}^N (\sum_{t=1}^N \nabla_\theta \log \pi_\theta (a_{i,t}|o_{i,t}))(\sum_{t=1}^T r(s_{i,t},a_{i,t}))

🔥

Markov property is not actually used so we can just use

o_{i,t}

in place of

s_{i,t}

What’s wrong?

Blue graph corresponds to PDF of reward, green bars represent samples of rewards, and dashed blue graph corresponds to fitted policy distribution

What if reward is shifted up (adding a constant) (while everything maintains the same)?

We see huge differences in fitted policy distributions ⇒ we have a high variance problem

How we can modify policy gradient to reduce variance?

🔥

Causality: policy at time

t’

cannot affect reward at time

t

t < t’

\nabla_\theta J(\theta) \approx \frac{1}{N}\sum_{i=1}^N\sum_{t=1}^T\nabla_\theta\log\pi_\theta(a_{i,t}|s_{i,t})(\sum_{t'=1}^T r(s_{i,t'},a_{i,t'}))

We want to show that the expectation of the previous rewards would converge to 0 so we can rewrite the summation. Note that removing those terms in finite time would change the estimator but it is still unbiased.

\nabla_\theta J(\theta) \approx \frac{1}{N}\sum_{i=1}^N\sum_{t=1}^T\nabla_\theta\log\pi_\theta(a_{i,t}|s_{i,t})\underbrace{(\sum_{t'=t}^T r(s_{i,t'},a_{i,t'}))}_{\mathclap{\text{reward to go $\hat{Q}_{i,t}$}}}

We have removed some items from the sum therefore the variance is lower.

With discount factors

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla _\theta \log \pi_\theta (a_{i,t}|s_{i,t}) (\sum_{t' = t}^T \gamma^{t' -t} r(s_{i,t'},a_{i,t}))

The power on the $\gamma$ ⇒ $t’ - t$ is important because now the gradient is NOT decresing with t stepping ⇒ we’re putting less focus on the future rewards in the current step, but in future steps those rewards will be valued more again.

If we let the power be $t’ - 1$ or $t-1$ ⇒ then as we train from $t=0$ to $t \rightarrow \infin$ , the gradient would decrease as $t$ increases

Baselines

We want policy gradients to optimize reward actions that are above average and penalize reward actions that are below average.

\begin{split} \nabla_\theta J(\theta) &\approx \frac{1}{N} \sum_{i=1}^N \nabla_\theta \log p_\theta (\tau)[r(\tau)-b] \end{split}

Without baseline (b = 0), but with baseline, set b as

b = \frac{1}{N}\sum_{i=1}^Nr(\tau)

Changing b will keep the esitimator unbiased but will change the variance!

\begin{split} \mathbb{E}[\nabla_\theta \log p_\theta(\tau)b] &= \int p_\theta(\tau)\nabla_\theta \log p_\theta(\tau) b d\tau \\ &= \int \nabla_\theta p_\theta(\tau)b d\tau \\ &= b \nabla_\theta \int p_\theta(\tau) d\tau \\ &=b\nabla_\theta1 = 0 \end{split}

Average reward is not the best baseline, but it’s pretty good!

Let’s first write down variance

\begin{split} Var &= \mathbb{E}_{\tau \sim p_\theta(\tau)}[(\nabla_\theta \log p_\theta(\tau)(r(\tau)-b))^2]-\mathbb{E}_{\tau \sim p_\theta(\tau)}[\nabla_\theta\log p_\theta (\tau)(r(\tau)-b)]^2 \\ \end{split}

\begin{split} \frac{dVar}{db} &=\frac{d}{db}\mathbb{E}[g(\tau)^2(r(\tau)-b)^2], g(\tau)=\text{gradient$(\log(\tau))$} \\ &=\frac{d}{db}(\mathbb{E}[g(\tau)^2r(\tau)^2]-2\mathbb{E}[g(\tau)^2r(\tau)b]+b^2\mathbb{E}[g(\tau)^2]) \\ &= -2\mathbb{E}[g(\tau)^2r(\tau)]+2b\mathbb{E}[g(\tau)^2]=0 \\ \end{split}

So optimal value of b

b = \frac{\mathbb{E}[g(\tau)^2r(\tau)]}{\mathbb{E}[g(\tau)^2]}

Intuition: Different baseline for every entry in the gradient, the baseline for every parameter value is the expected value of the reward weighted by the magnitude of the gradient for the parameter value

Off-policy setting

Policy gradient is defined to be on-policy

The expectatio causes us to need to update samples every time we have updated the policy, but problem is Neural Nets only change a bit with each gradient step.

So we can modify the policy a bit

Instead of having samples from $p_\theta(\tau)$ , we have samples from $\bar{p}(\tau)$

We can use importance sampling to accomodate this case

\begin{split} \mathbb{E}_{x \sim p(x)}[f(x)] &= \int \mathbb{P}_p(x)f(x)dx \\ &=\int \frac{\mathbb{P}_q (x)}{\mathbb{P}_q (x)} \mathbb{P}_p (x) f(x) dx \\ &=\int \mathbb{P}_q(x) \frac{\mathbb{P}_p(x)}{\mathbb{P}_q(x)}f(x)dx \end{split}

Due to this expectation, we see that our objective becomes this

J(\theta)=\mathbb{E}_{\tau \sim \bar{p}(\tau)}[\frac{p_\theta(\tau)}{\bar{p}(\tau)}r(\tau)]

Where

p_\theta(\tau)=p(s_1)\prod_{t=1}^T \pi_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t)

Therefore,

\begin{split} \frac{p_\theta(\tau)}{\bar{p}(\tau)} &= \frac{p(s_1)\prod_{t=1}^T \pi_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t)}{p(s_1)\prod_{t=1}^T \bar{\pi}_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t)} \\ &=\frac{\prod_{t=1}^T \pi_\theta(a_t|s_t)}{\prod_{t=1}^T \bar\pi_\theta(a_t|s_t)} \end{split}

So… we can estimate the value of some new parameters $\theta '$

J(\theta')=\mathbb{E}_{\tau \sim p_{\theta}(\tau)}[\frac{p_{\theta'}(\tau)}{p_\theta(\tau)} r(\tau)]

\begin{split} \nabla_{\theta '} J(\theta ') &= \mathbb{E}_{\tau \sim p_\theta(\tau)} [\frac{\nabla_{\theta '} p_{\theta '}(\tau)}{p_\theta(\tau)}r(\tau)] \\ &=\mathbb{E}_{\tau \sim p_\theta(\tau)} [\frac{p_{\theta '}(\tau)}{p_\theta(\tau)}\nabla_{\theta '} \log p_{\theta '} (\tau) r(\tau)] \\ &=\mathbb{E}_{\tau \sim p_\theta(\tau)}[(\prod_{t=1}^T\frac{\pi_{\theta '}(a_t|s_t)}{\pi_\theta(a_t|s_t)})(\sum_{t=1}^T \nabla_{\theta '} \log \pi_{\theta '}(a_t|s_t))(\sum_{t=1}^T r(s_t,a_t))] \end{split}

We can consider causality(the fact that current action does not affect past rewards) and

\begin{split} \nabla_{\theta '} J(\theta ') &=\mathbb{E}_{\tau \sim p_\theta(\tau)}[\sum_{t=1}^T \nabla_{\theta '} \log \pi_{\theta '}(a_t|s_t)(\prod_{t'=1}^t \frac{\pi_{\theta '} (a_{t'}|s_{t'})}{\pi_\theta(a_{t '}|s_{t '})})(\sum_{t' = t}^Tr(s_{t'},a_{t'})(\prod_{t''=t}^{t'}\frac{\pi_{\theta '}(a_{t ''}|s_{t ''})}{\pi_\theta(a_{t ''} | s_{t ''})}))] \end{split}

Some important terms in this equation:

$\prod_{t’=1}^t \frac{\pi_{\theta ‘}(a_{t ‘} | s_{t ’})}{\pi_{\theta}(a_{t ‘} | s_{t ’})}$ ⇒ future actions won’t affect current weight ⇒ however, looks like we still have the term at the end ⇒ its also a trouble because it’s exponential in $T$

$\prod_{t''=t}^{t'}\frac{\pi_{\theta '}(a_{t ''}|s_{t ''})}{\pi_\theta(a_{t ''} | s_{t ''})}$ ⇒ we cannot complete ignore this because stripping this term would not be gradient descent but actually”Policy Iteration” algorithm

Since the first term is exponential, we can try to write the objetive a bit differently

On-policy policy gradient

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t}) \hat{Q}_{i,t}

Off-policy policy gradient

\begin{split} \nabla_{\theta '} J(\theta ') &\approx \frac{1}{N}\sum_{i=1}^N\sum_{t=1}^T \frac{\pi_{\theta '} (s_{i,t}, a_{i,t})}{\pi_\theta(s_{i,t},a_{i,t})} \nabla_{\theta '} \log \pi_{\theta '}(a_{i,t}|s_{i,t}) \hat{Q}_{i,t} \\ &\quad = \frac{1}{N}\sum_{i=1}^N \sum_{t=1}^T \underbrace{\frac{\pi_{\theta '}(s_{i,t})}{\pi_\theta(s_{i,t})}}_{\mathclap{\text{Can we ignore this part?}}} \frac{\pi_{\theta '}(a_{i,t}|s_{i,t})}{\pi_\theta(a_{i,t}|s_{i,t})} \nabla_{\theta '} \log \pi_{\theta '}(a_{i,t}|s_{i,t}) \hat{Q}_{i,t} \end{split}

This does not necessarily give the optimal policy, but its a reasonable approximation.

Policy Gradient with Automatic Differentiation

We don’t want to be inefficient at computing gradients ⇒ use backprop trick

So why don’t we start from the MLE approach to Policy Gradients?

\nabla_\theta J_{ML} \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta (a_{i,t}|s_{i,t})

To start doing backprop, let’s define the objective function first.

J_{ML}(\theta) \approx \frac{1}{N}\sum_{i=1}^N \sum_{t=1}^T \log \pi_\theta (a_{i,t}|s_{i,t})

So we will define our “pseudo-loss” approximation as weighted maximum likelihood

\tilde{J}(\theta) \approx \frac{1}{N}\sum_{i=1}^N \sum_{t=1}^T \log \pi_\theta (a_{i,t}|s_{i,t}) \hat{Q}_{i,t}

A few reminders about tuning hyper-parameters

Gradients has very high variance
1. Isn’t the same as supervised learning

Consider using much larger batches

Tweaking learning rates is VERY hard
1. Adaptive step size rules like ADAM can be OK-ish

Covariant/natural policy gradient

🤔

One thing about one dimension state and action spaces are that you can visualize the policy distribution easily one a 2d plane

\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)

We can view the first order gradient descent as follows

\theta ' \leftarrow \argmax_{\theta '} (\theta ' - \theta)^{\top}\nabla_{\theta}J(\theta) \\ \text{s.t. } ||\theta ' - \theta||^2 \le \epsilon

Thank about $\epsilon$ as a high-dimensional sphere.

We can instead put constraint on the distribution of the policy

\theta ' \leftarrow \argmax_{\theta '} (\theta ' - \theta)^{\top}\nabla_{\theta}J(\theta) \\ \text{s.t. } D(\pi_{\theta '}, \pi_\theta) \le \epsilon

Where $D(\cdot, \cdot)$ is a distribution dimension measure.

So we want to choose some parameterization-independent divergence measure

Usually KL-divergence

D_{KL}(\pi_{\theta '}||\pi_\theta) = \mathbb{E}_{\pi_{\theta '}}[\log \pi_\theta - \log \pi_{\theta '}]

A but hard to plug into our gradient descent ⇒ we will approximate this distance using 2nd order Taylor expansion around the current parameter value $\theta$

Advanced Policy Gradients

Why does policy gradient work?

Estimate $\hat{A}^\pi (s_t,a_t)$ (Monte-carlo or function approximator) for current policy $\pi$

Use $\hat{A}^\pi(s_t,a_t)$ to get improved policy $\pi '$

We are going back and forth between (1) and (2)

Looks familiar to policy iteration algorithm!

Nice thing about policy gradients:

If advantage estimator is perfect, we are just moving closer to the “optimal” policy for the advantage estimator not jumping to the optimal

But how do we formalize this?

If we set the loss function of policy gradient as

J(\theta) = \mathbb{E}_{\tau \sim p_\theta(\tau)}[\sum_t \gamma^t r(s_t,a_t)]

Then we can calculate how much we improved by

J(\theta ') - J(\theta) = \mathbb{E}_{\tau \sim p_{\theta'}(\tau)}[\sum_t \gamma^t A^{\pi_\theta}(s_t,a_t)]

Here we claimed that $J(\theta’) - J(\theta)$ is equal to the expectation of all discounted advantage estimates in the new trajectory that the new policy would explore.

We will prove by:

\begin{split} J(\theta')-J(\theta)&=J(\theta')-\mathbb{E}_{s_0 \sim p(s_0)} [V^{\pi_\theta}(s_0)] \\ &= J(\theta') - \underbrace{\mathbb{E}_{\tau \sim p_{\theta '}(\tau)}[V^{\pi_\theta}(s_0)]}_{\mathclap{\text{It's the same as above because the initial states $s_0$ are the same}}} \\ &= J(\theta') - \mathbb{E}_{\tau \sim p_{\theta'}(\tau)}[\sum_{t=0}^\infin \gamma^t V^{\pi_\theta}(s_t) - \sum_{t=1}^\infin \gamma^t V^{\pi_\theta}(s_t)] \\ &= J(\theta') + \mathbb{E}_{\tau \sim p_{\theta'}(\tau)}[\sum_{t=0}^\infin \gamma^t (\gamma V^{\pi_\theta}(s_{t+1}) - V^{\pi_\theta}(s_t))] \\ &= \mathbb{E}_{\tau \sim p_{\theta'}(\tau)}[\sum_{t=0}^\infin \gamma^t r(s_t,a_t)] + \mathbb{E}_{\tau \sim p_{\theta'}(\tau)}[\sum_{t=0}^\infin \gamma^t (\gamma V^{\pi_\theta}(s_{t+1}) - V^{\pi_\theta}(s_t))] \\ &= \mathbb{E}_{\tau \sim p_{\theta'}(\tau)}[\sum_{t=0}^\infin \gamma^t (r(s_t,a_t) + \gamma V^{\pi_\theta}(s_{t+1}) - V^{\pi_\theta}(s_t))] \\ &= \mathbb{E}_{\tau \sim p_{\theta'}(\tau)}[\sum_{t=0}^\infin \gamma^t A^{\pi_\theta}(s_t,a_t)] \end{split}

🔥

This proof shows that by optimizing

\mathbb{E}_{\tau \sim p_{\theta’}}[\sum_t \gamma^t A^{\pi_\theta}(s_t,a_t)]

, we are actually improving our policy

But how does this relate to our policy gradient?

\begin{split} \mathbb{E}_{\tau\ \sim p_{\theta'}(\tau)}[\sum_t \gamma^t A^{\pi_\theta}(s_t,a_t)] &= \sum_t \mathbb{E}_{s_t \sim p_{\theta'}(s_t)} [\mathbb{E}_{a_t \sim \pi_{\theta '}(a_t|s_t)}[\gamma^t A^{\pi_\theta} (s_t,a_t)]] \\ &= \sum_t \mathbb{E}_{s_t \sim p_{\theta'}(s_t)} [\underbrace{\mathbb{E}_{a_t \sim \pi_{\theta}(a_t|s_t)}[\frac{\pi_{\theta '}(a_t|s_t)}{\pi_\theta(a_t|s_t)}}_{\mathclap{\text{importance sampling}}} \gamma^t A^{\pi_\theta} (s_t,a_t)]] \\ &\approx \sum_t \underbrace{\mathbb{E}_{s_t \sim p_{\theta}(s_t)}}_{\mathclap{\text{ignoring distribution mismatch}}} [\mathbb{E}_{a_t \sim \pi_{\theta}(a_t|s_t)}[\frac{\pi_{\theta '}(a_t|s_t)}{\pi_\theta(a_t|s_t)} \gamma^t A^{\pi_\theta} (s_t,a_t)]] \\ &\quad =\bar{A}(\theta') \end{split}

We want this approximation to be true so that

J(\theta')-J(\theta) \approx \bar{A}(\theta')

And then we can use

\theta' \leftarrow \argmax_{\theta'} \bar{A}(\theta)

to optimize our policy

And use $\hat{A}^\pi(s_t,a_t)$ to get improved policy $\pi’$

But when is this true?

Bounding the distribution change (deterministic)

We will show:

🔥

p_\theta(s_t)

is close to

p_{\theta’}(s_t)

when

\pi_\theta

is close to

\pi_\theta’

We will assume that $\pi_\theta$ is a deterministic policy $a_t = \pi_\theta(s_t)$

We define closeness of policy as:

$\pi_{\theta’}$ is close to $\pi_\theta$ if $\pi_{\theta’}(a_t \ne \pi_\theta(s_t)|s_t) \le \epsilon$

p_{\theta'}(s_t) = \underbrace{(1-\epsilon)^t}_{\mathclap{\text{probability we made no mistakes}}} p_\theta(s_t)+(1-(1-\epsilon)^t)\underbrace{p_{mistake}(s_t)}_{\mathclap{\text{some other distribution}}}

Implies that we can write the total variation divergence as

\begin{split} |p_{\theta'}(s_t)-p_\theta(s_t)| &= (1-(1-\epsilon)^t) |p_{mistake}(s_t)-p_\theta(s_t)| \\ &\le 2(1-(1-\epsilon)^t) \\ &\le 2\epsilon t \end{split}

👉

Useful Identity

\forall \epsilon \in [0,1], (1-\epsilon)^t \ge 1 - \epsilon t

Bounding the distribution change (arbitrary)

Schulman, Levine, Moritz, Jordan, Abbeel, “Trust Region Policy Optimization”

We will show:

🔥

p_\theta(s_t)

is close to

p_{\theta’}(s_t)

when

\pi_\theta

is close to

\pi_\theta’

Closeness:

$\pi_{\theta’}$ is close to $\pi_\theta$ if $|\pi_{\theta’}(a_t|s_t) - \pi_\theta(a_t|s_t)| \le \epsilon$ for all $s_t$

Useful Lemma:

If $|p_X(x) - p_Y(y)| = \epsilon$ , there exists $p(x,y)$ such that $p(x) = p_X(x)$ and $p(y) = p_Y(y)$ and $p(x=y) = 1 - \epsilon$

Says:

$p_X(x)$ agrees with $p_Y(y)$ with probability $\epsilon$

$\pi_{\theta'}(a_t|s_t)$ takes a different action than $\pi_{\theta}(a_t|s_t)$ with probability at most $\epsilon$

Therefore

\begin{split} |p_{\theta'}(s_t)-p_{\theta}(s_t)| &= (1-(1-\epsilon)^t)|p_{mistake}(s_t)-p_\theta(s_t)| \\ &\le 2(1-(1-\epsilon)^t) \\ &\le 2 \epsilon t \end{split}

Bounding the objective value

Assume $|p_{\theta’}(s_t)-p_{\theta}(s_t)| \le 2\epsilon t$

\begin{split} \mathbb{E}_{s_t \sim p_{\theta'}(s_t)}[f(s_t)] &= \sum_{s_t} p_{\theta'}(s_t)f(s_t) \\ &\ge \sum_{s_t} p_{\theta}(s_t)f(s_t) - |p_{\theta}(s_t)-p_{\theta'}(s_t)|\max_{s_t}f(s_t) \\ &\ge \mathbb{E}_{p_\theta(s_t)}[f(s_t)] - 2\epsilon t \max_{s_t} f(s_t) \end{split}

For the objective value, we can bound it by

\begin{split} \mathbb{E}_{\tau\ \sim p_{\theta'}(\tau)}[\sum_t \gamma^t A^{\pi_\theta}(s_t,a_t)] &= \sum_t \mathbb{E}_{s_t \sim p_{\theta'}(s_t)} [\underbrace{\mathbb{E}_{a_t \sim \pi_{\theta}(a_t|s_t)}[\frac{\pi_{\theta '}(a_t|s_t)}{\pi_\theta(a_t|s_t)}}_{\mathclap{\text{importance sampling}}} \gamma^t A^{\pi_\theta} (s_t,a_t)]] \\ & \ge \sum_t \mathbb{E}_{s_t \sim p_{\theta}(s_t)} [\mathbb{E}_{a_t \sim \pi_{\theta}(a_t|s_t)}[\frac{\pi_{\theta '}(a_t|s_t)}{\pi_\theta(a_t|s_t)} \gamma^t A^{\pi_\theta} (s_t,a_t)]] - \sum_{t} 2\epsilon tC \\ \end{split}

Where $C$ is a constant being the largest value that the thing in the state exepectation can take on ⇒ its a probability times an advantage ⇒ largest possible reward times the number of time steps.

So:

C \in O(Tr_{max}) \text{ or } \underbrace{O(\frac{r_{max}}{1-\gamma})}_{\mathclap{\text{infinite time with discount (geometric series)}}}

Therefore for small enought $\epsilon$ , $\bar{A}^{\pi}(\theta ')$ is guarenteed to be similar to the true RL objective

Policy Gradients with Constraints

We want to constrain:

|\pi_{\theta'}(a_t|s_t) - \pi_{\theta}(a_t|s_t)| \le \epsilon

It which will result in

|p_{\theta'}(s_t)-p_\theta(s_t)| \le 2\epsilon t

A more convenient bound:

|\pi_{\theta'}(a_t|s_t) - \pi_{\theta}(a_t|s_t)| \le \sqrt{\frac{1}{2} D_{KL}(\pi_{\theta'}(a_t|s_t),\pi_{\theta}(a_t|s_t))}

We see that the KL divergence bounds the state marginal difference

Note:

D_{KL}(p_1(x),p_2(x)) = \mathbb{E}_{x \sim p_1(x)} [\log \frac{p_1(x)}{p_2(x)}]

👉

KL Divergence has very convenient properties that make it much easier to approximate

So contraining our objective, we have:

\theta' \leftarrow \argmax_{\theta'} \sum_t \mathbb{E}_{s_t \sim p_{\theta}(s_t)}[\mathbb{E}_{a_t \sim \pi_\theta(a_t|s_t)}[\frac{\pi_{\theta'}(a_t|s_t)}{\pi_\theta(a_t|s_t)}\gamma^t A^{\pi_\theta} (s_t,a_t)]] \\ \text{s.t. } D_{KL}(\pi_{\theta '}(a_t|s_t), \pi_\theta(a_t|s_t)) \le \epsilon

For small $\epsilon$ , this is guaranteed to improve $J(\theta’) - J(\theta)$

👉

We can do this by simply write out the lagrangian function and do convex optimization

L(\theta',\lambda) = \sum_t \mathbb{E}_{s_t \sim p_{\theta}(s_t)}[\mathbb{E}_{a_t \sim \pi_\theta(a_t|s_t)}[\frac{\pi_{\theta'}(a_t|s_t)}{\pi_\theta(a_t|s_t)}\gamma^t A^{\pi_\theta} (s_t,a_t)]] - \lambda(D_{KL}(\pi_{\theta '}(a_t|s_t), \pi_\theta(a_t|s_t)) - \epsilon)

“Dual Gradient Descent” Alternate between:

Maximize $L(\theta’, \lambda)$ with respect to $\theta’$

$\lambda \leftarrow \lambda + \alpha(D_{KL}(\pi_{\theta’}(a_t|s_t),\pi_\theta(a_t|s_t)) - \epsilon)$

Intuition: raise $\lambda$ if constraint is violated too much

Natural Gradient

As usual, we denote $\bar{A}(\theta’)$ as

\bar{A}(\theta') = \sum_t \mathbb{E}_{s_t \sim p_{\theta}(s_t)}[\mathbb{E}_{a_t \sim \pi_\theta(a_t|s_t)}[\frac{\pi_{\theta'}(a_t|s_t)}{\pi_\theta(a_t|s_t)}\gamma^t A^{\pi_\theta} (s_t,a_t)]]

When we are doing gradient descent, we are actually optimizing near a region(trust region) in the first order taylor expansion of the objective.

Can we use this fact to simplify the optimization step and use one easy algorithm to take care of this constrained optimization problem?

\theta' \leftarrow \argmax_{\theta'} \nabla_{\theta} \bar{A}(\theta)^{\top}(\theta'-\theta) \\ \text{s.t. } D_{KL}(\pi_{\theta'}(a_t|s_t),\pi_{\theta}(a_t|s_t)) \le \epsilon

Let’s look at the gradient of $\bar{A}(\theta’)$

\nabla_{\theta'}\bar{A}(\theta) = \sum_t \mathbb{E}_{s_t \sim p_\theta(s_t)}[\mathbb{E}_{a_t \sim \pi_\theta(a_t|s_t)}[\frac{\pi_{\theta'}(a_t|s_t)}{\pi_\theta(a_t|s_t)}\gamma^t \nabla_\theta \log \pi_\theta(a_t|s_t) A^{\pi_\theta}(s_t,a_t)]] \\

Evaluating this at point $\theta’ = \theta$

\begin{split} \nabla_{\theta}\bar{A}(\theta) &= \sum_t \mathbb{E}_{s_t \sim p_\theta(s_t)}[\mathbb{E}_{a_t \sim \pi_\theta(a_t|s_t)}[\gamma^t \nabla_\theta \log \pi_\theta(a_t|s_t) A^{\pi_\theta}(s_t,a_t)]] \\ &= \nabla_\theta J(\theta) \end{split}

Can we just use the gradient then?

Remember in the original policy gradient algorithm, $\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$

But some parameters change probabilities a lot more than others, we are not considering the KL Divergence in this case

⚠️

so we want to either form the policy to let them have equal effects, or we can change the learning rate for each of the parameters

But it seems like the problem can be fixed, notice that

Gradient Descent still poses some kind of constraint $||\theta - \theta’||^2 \le \epsilon$

Think about in parameter space, we are constrained to within some fixed distance(inside a circle) from the original parameter. ⇒ Indeed the learning rate $\alpha = \sqrt{\frac{\epsilon}{||\nabla_\theta J(\theta)||^2}}$ can satisfy this constraint.

But in KL divergence, maybe we want an ellipse? (we want a circle in distribution space)

We will use second order taylor expansion to approximate the KL divergence to make it easier to calculate.

D_{KL}(\pi_{\theta '} || \pi_\theta) \approx (\theta '-\theta)\underbrace{F}_{\mathclap{\text{Fisher-information Matrix}}}(\theta ' - \theta)

F = \mathbb{E}_{\pi_{\theta}}[\nabla_\theta \log \pi_\theta(a|s) \nabla_\theta \log \pi_\theta(a|s)^{\top}]

Now we see that the shape of the new ellipse in parameter space is determined by the matrix $F$

We can estimate this $F$ expectation using samples

So therefore!

Using the approximation, our policy becomes

\theta \leftarrow \argmax_{\theta '} (\theta ' - \theta)^{\top}\nabla_\theta J(\theta) \\ \text{s.t. } ||\theta ' - \theta||_F^2 \le \epsilon

With this we have the “natural gradeint”

\theta \leftarrow \theta + \alpha F^{-1} \nabla_\theta J(\theta)

If we want to enforce the constraint, we can choose a step size that enforces the constraint.

We can calculate step size $\alpha$ by

\alpha = \sqrt{\frac{2 \epsilon}{\nabla_\theta J(\theta)^{\top} F \nabla_\theta J(\theta)}}

Or run conjugate gradient method to calculate inverse $\nabla_\theta J(\theta)$ and get $\alpha$ as a by-product (see trust region policy optimization paper)

Several policy that utilizes this trick:

natural gradient: pick $\alpha$

trust region policy optimization: pick $\epsilon$

Can solve for optimal $\alpha$ while solving $F^{-1} \nabla_\theta J(\theta)$

Conjugate gradient works well for this

Actor-Critic Method

Remember from the policy gradient that

\begin{split} \nabla_\theta J(\theta)&=\mathbb{E}_{\tau \sim p_\theta(\tau)}[(\sum_{t=1}^T\nabla_\theta \log \pi_\theta(a_t|s_t))(\sum_{t=1}^Tr(s_t,a_t))] \\ &\approx \frac{1}{N}\sum_{i=1}^N(\sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t})(\underbrace{\sum_{t=1}^T r(s_{i,t},a_{i,t})}_{\mathclap{\text{Reward to go $\hat{Q}_{i,t}$}}}) \end{split}

$\hat{Q}_{i,t}$ is the estimate of expected reward if we take action $a_{i,t}$ in state $s_{i,t}$

But $\hat{Q}_{i,t}$ currently has a very high variance

$\hat{Q}_{i,t}$ is only taking account of a specific chain of action-state pairs
1. This is because we approximated the gradient by stripping away the expectation

We can get a better estimate by using the true expected reward-to-go

Q^{\pi}(s_t,a_t)=\sum_{t'=t}^T \mathbb{E}_{\pi_\theta}[r(s_{t '},a_{t'})|s_t,a_t]

What about baseline? Can we apply a baseline even if we have a true Q function?

V^{\pi}(s_t)=\mathbb{E}_{a_t \sim \pi_\theta(a_t|s_t)}[Q^{\pi}(s_t,a_t)]

Turns out that we can do better(less variance) than applying $b_t = \frac{1}{N} \sum_i Q(s_{i,t},a_{i,t})$ because with the value function, the baseline can be dependent on the state.

So now our gradient becomes

\begin{split} \nabla_\theta J(\theta) &\approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t}) \underbrace{(Q^{\pi}(s_{i,t},a_{i,t})-V^{\pi}(s_{i,t}))}_{\mathclap{\text{How much better the action $a_{i,t}$ is than the average action}}} \\ &\approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t}) A^{\pi}(s_{i,t},a_{i,t}) \end{split}

We will also name something new: the advantage function:

How much better the action $a_{i,t}$ is than the average action

A^{\pi}(s_t,a_t)=Q^{\pi}(s_t,a_t)-V^{\pi}(s_t)

The better estimate $A^{\pi}$ estimate has, the lower variance $\nabla_\theta J(\theta)$ has.

Fitting Q/Value/Advantage Functions

But problem is, what should we fit? $Q^{\pi}, V^{\pi}, A^{\pi}$ ?

Let’s do some approximation and find out

\begin{split} Q^{\pi}(s_t,a_t)&=r(s_t,a_t)+\gamma\mathbb{E}_{s_{t+1} \sim p(s_{t+1}|s_t,a_t)}[V^{\pi}(s_{t+1})] \\ &\approx r(s_t,a_t)+\gamma V^{\pi}(s_{t+1}) \end{split}

A^{\pi} \approx r(s_t,a_t)+\gamma V^{\pi}(s_{t+1})-V^{\pi}(s_t)

We will introduce what $\gamma$ (discount factor) is later. Just view it as $\gamma=1$ for now.

So now we see that it is now easy to fit $V^{\pi}$ and use $V^{\pi}$ to approximate $Q^{\pi}$ and $A^{\pi}$ .

$V^{\pi}$ is relatively easier to fit to because it does not involve action, only depends on state.

🔥

Note that Actor-Critic can also fit

Q^{\pi}

Policy Evaluation

This is what policy gradient does

V^{\pi}(s_t) \approx \sum_{t' = t}^T r(s_{t '}, a_{t' })

Ideally we want to do this:

V^{\pi}(s_t) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t'=t}^T r(s_{t'},a_{t'})

Because in a model-free setting we cannot reset back to a state and run multiple trials

Expectation of rewards

So…

Monte Carlo policy evaluation

Use empirical returns to train the a value function to approximate the expectation

Instead of using those rewards directly to a policy gradient we will fit a model to those rewards ⇒ will reduce variance

Because even though we cannot visit the same state twice, the function approximator will combine information with similar states

And we can of course use MSE, etc. - supervised training losses

Ideal target

y_{i,t} = \sum_{t'=t}^T \mathbb{E}_{\pi_\theta}[r(s_{t'},a_{t'})|s_{i,t}] \approx r(s_{i,t},a_{i,t})+\sum_{t' = t+1}^T \mathbb{E}_{\pi_\theta}[r(s_{t'},a_{t'})|s_{i,t+1}]

Monte Carlo target:

y_{i,t} = \sum_{t' = t}^T r(s_{i,t'},a_{i,t'})

Training data would be:

\{(s_{i,t},\underbrace{\sum_{t'=t}^T r(s_{i,t'},a_{i,t'})}_{\mathclap{\text{$y_{i,t}$}}})\}

We can do even better (bootstrapped estimate):

Hmmm… looks like we can modify a bit in the ideal target

y_{i,t} = \sum_{t'=t}^T \mathbb{E}_{\pi_\theta}[r(s_{t'},a_{t'})|s_{i,t}] \approx r(s_{i,t}, a_{i,t}) + V^{\pi}(s_{i,t+1})

Since we don’t know $V^{\pi}$ , we can approximate it by $\hat{V}_{\phi}^{\pi}(s_{i,t+1})$ - our previous value function approximator (bootstraped estimate)

y_{i,t} = \sum_{t'=t}^T \mathbb{E}_{\pi_\theta}[r(s_{t'},a_{t'})|s_{i,t}] \approx r(s_{i,t}, a_{i,t}) + \hat{V}_{\phi}^{\pi}(s_{i,t+1})

So now training data:

\{(s_{i,t},r(s_{i,t},a_{i,t})+\hat{V}^{\pi}_{\psi} (s_{i,t+1})\}

🔥

Lower variance than Monte Carlo evaluation, but higher bias (because

\hat{V}_{\phi}^{\pi}

might be incorrect)

Batch actor-critic algorithm

⚠️

The fitted value function is not guarenteed to merge, same reason as the section “Value Function Learning Theory”

Discount Factor

If $T \rightarrow \infin$ , $\hat{V}_\phi^\pi$ ⇒ the approximator for $V^{\pi}$ can get infinitely large in many cases, so we can regulate the reward to be “sooner rather than later”.

y_{i,t} \approx r(s_{i,t},a_{i,t}) + \gamma \hat{V}_\phi^\pi(s_{i,t+1})

Where $\gamma \in [0,1]$ is the discount factor, it let’s reward you get decay in every timestep ⇒ So that the obtainable reward in infinite lifetime can actually be bounded.

One understanding that $\gamma$ affects policy is that $\gamma$ adds a “death state” that once you’re in, you can never get out.

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t})(\sum_{t' = t}^T \gamma^{t' - t} r(s_{i,t'},a_{i,t'}))

Online Actor-critic Algorithm

In practice:

Off-policy Actor-critic algorithms

Idea: Collect data and instead of training on them directly, put them into a replay buffer. At training instead of using the data just collected, fetch one randomly from the replay buffer.

Coming from the online algorithm, let’s see what problems do we need to fix:

(1) Under current policy, it is possible that our policy would not even have taken the next action $a_i$ and therefore it’s not cool to assume we will arrive at the reward $r(s_i,a_i,s_i')$ ⇒ We may not even arrive at state $s_i’$

(2) Same reason, we may not have taken $a_i$ as our action under the current policy

We can fix the problem in (1) by using $Q^{\pi}(s_t,a_t)$ ⇒ replace the term $\gamma \hat{V}_\phi^\pi(s_i’)$

Now

L(\phi)=\frac{1}{N}\sum_i ||\hat{Q}_\phi^\pi(s_i,a_i)-y_i)||^2

And we replace the target value

y_i = r_i + \gamma \hat{Q}^\pi_\phi (s_i',\underbrace{a_i'^\pi}_{\mathclap{\text{this is sampled from current policy, $a_i'\sim \pi_\theta(a_i'^\pi|s_i')$}}})

Same for (2), sample an action from current policy $a_i^\pi \sim \pi_\theta(a_i|s_i)$ rather than using the original data

And instead of plugging in advantage function,

\begin{split} \nabla_\theta J(\theta) &\approx \frac{1}{N} \sum_i \nabla_\theta \log \pi_\theta (a_i^\pi|s_i) \hat{A}^{\pi}(s_i,a_i^\pi) \\ &\approx \frac{1}{N} \sum_i \nabla_\theta \log \pi_\theta (a_i^\pi|s_i) \underbrace{\hat{Q}^{\pi}(s_i,a_i^\pi)}_{\mathclap{\text{Higher variance}}} \\ \end{split}

It’s fine to have high variance (not being baselined), because it’s easier and now we don't need to generate more states ⇒ we can just generate more actions

In exchange use a larger batch size ⇒ all good!

🔥

Still one problem left ⇒

s_i

did not come from

p_\theta(s)

⇒ but nothing we can do Not too bad ⇒ Initially we want optimal policy on

p_\theta(s)

, but we actually get optimal policy on a broader distribution

Now our final result:

Example Practical Algorithm: Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, Sergey Levine. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor. 2018.

Critics as state-dependent baselines

In actor-critic

\begin{split} \nabla_\theta J(\theta) &\approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t}) (Q^{\pi}(s_{i,t},a_{i,t})-V^{\pi}(s_{i,t})) \\ &\approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t}) A^{\pi}(s_{i,t},a_{i,t}) \end{split}

This method of using fitted model to approximate value/Q/Advantage Function:

Lowers variance

Biased as long as the critic is not perfect

In policy gradient:

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta (a_{i,t}|s_{i,t})((\sum_{t'=t}^T \gamma^{t'-t}r(s_{i,t'},a_{i,t'}))-b)

This method:

No bias

High variance

So we can use a state-dependent baseline to still keep the estimator unbiased but reduce a bit variance?

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta (a_{i,t}|s_{i,t}) ((\sum_{t'=t}^T \gamma^{t'-t} r(s_{i,t'},a_{i,t'}))-\hat{V}_\phi^\pi(s_{i,t}))

Not only does the policy gradient remain unbiased when you subtract any constant b, it still remains unbiased when you subtract any function that only depends on the state $s_{i}$ (and not on the action)

Control variates - methods that use state and action dependent baselines

\hat{A}^{\pi}(s_t) = \sum_{t'=t}^\infin \gamma^{t'-t}r(s_{t'},a_{t'})-V_\phi^\pi(s_t)

No bias

Higher variance (because single-sample estimate)

\hat{A}^\pi(s_t,a_t)=\sum_{t'=t}^\infin \gamma^{t'-t}r(s_{t'},a_{t'})-Q_\phi^\pi(s_t,a_t)

Goes to zero in expectation if critic is correct

If critic is not correct, bomb shakalaka
1. The expectation integrates to an error term that needs to be compensated for

To account for the error in baseline, we modify it to:

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{i=1}^T \nabla_\theta \log \pi_\theta (a_{i,t}|s_{i,t})(\hat{Q}_{i,t}-Q_\phi^\pi(s_{i,t},a_{i,t})) + \frac{1}{N}\sum_{i=1}^N\sum_{t=1}^T \nabla_\theta \mathbb{E}_{a \sim \pi_\theta(a_t,s_{i,t})}[Q^{\pi}_\phi(s_{i,t},a_t)]

Use a critic without the bias, provided second term can be evaluated Gu et al. 2016 (Q-Prop)

Eligibility traces & n-step returns

Again, the Critic advantage estimator

\hat{A}_C^\pi(s_t,a_t)=r(s_t,a_t)+\gamma \hat{V}_\phi^\pi(s_{t+1})-\hat{V}_\phi^\pi(s_t)

Lower variance

higher bias if value estimate is wrong

The Monte Carlo Advantage Estimator

\hat{A}_{MC}^\pi(s_t,a_t) = \sum_{t'=t}^\infin \gamma^{t'-t} r(s_{t'},a_{t'})-\hat{V}_\phi^\pi(s_t)

unbiased

higher variance (single-sample estimate)

Get something in-between?

Facts:

rewards are smaller as $t’ \rightarrow \infin$
1. So biases are much smaller problems when $t’$ is big

Variance is more of a problem in the future

\hat{A}_n^\pi(s_t,a_t)=\sum_{t'=t}^{t+n} \gamma^{t'-t}r(s_{t'},a_{t'})+\gamma^{n}\hat{V}_\phi^\pi(s_{t+n})-\hat{V}_\phi^\pi(s_t)

Generalized advantage estimation

The n-step advantage estimator is good, but can we generalize(hybrid) it?

Instead of hard cutting between two estimators, why don’t we combine them everywhere?

\hat{A}_{GAE}^{\pi}(s_t,a_t) = \sum_{n=1}^\infin w_n \hat{A}_n^\pi(s_t,a_t)

Where $\hat{A}_n^\pi$ stands for the n-step estimator

“Most prefer cutting earlier (less variance)”

So we set $w_n \propto \lambda^{n-1}$ ⇒ exponential falloff

Then

\begin{split} \hat{A}_{GAE}^\pi(s_t,a_t)=\sum_{t'=t}^\infin (\gamma \lambda)^{t'-t} \delta_{t'} \\ \text{, where } \delta_{t '}=r(s_{t '},a_{t'})+\gamma\hat{V}_\phi^\pi(s_{t'+1})-\hat{V}_\phi^\pi(s_{t'}) \end{split}

🔥

Now we can just tradeoff the bias and variances using the parameter

\lambda

Examples of actor-critic algorithms

Schulman, Moritz, Levine, Jordan, Abbeel ‘16. High dimensional continuous control with generalized advantage estimation

Batch-mode actor-critic

Blends Monte Carlo and GAE

Mnih, Badia, Mirza, Graves, Lillicrap, Harley, Silver, Kavukcuoglu ‘16. Asynchronous methods for deep reinforcement learning

Online actor-critic, parallelized batch

CNN end-to-end

N-step returns with N=4

Single network for actor and critic

Value Function / Q Function Fitting (Value-Based)

Can we omit policy gradient completely from actor-critic methods?

Actor-critic minimizes

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta (a_{i,t}|s_{i,t}) (\sum_{t'=t}^T A(s_{t'},a_{t'}))

But the best policy can just be extracted from $\argmax_{a_t} A^{\pi}(s_t,a_t)$

\pi'(a_t|s_t)=\begin{cases} 1 &\quad \text{if } a_t = \argmax_{a_t} A^{\pi}(s_t,a_t) \\ 0 &\quad \text{otherwise} \end{cases}

We know that $\pi '$ is as good as $\pi$ , and probably better.

Same as before,

A^\pi(s,a)=r(s,a)+\gamma \mathbb{E}[V^{\pi}(s')] - V^{\pi}(s)

Policy Iteration (Fitted Value Iteration)

So fitting value function can be done if we know the transition dynamics very easily using least square estimate… but what if we don’t know transition dynamics?

Policy Iteration without transition probability (Fitted Q-Iteration)

What if we change the policy evalution part to

Q^\pi(s,a) \leftarrow r(s,a)+\gamma \mathbb{E}_{s' \sim p(s'|s,a)}[Q^\pi(s',\pi(s'))]

Now ⇒ if we have an $(s,a,r,s’)$ tuple then even if policy $\pi '$ changes its action in state $s$ we can still do policy evalution on the tuple because the only place the policy shows up is inside the expectation.

This simple change allows us to policy iteration style algorithms without actually knowing the transition dynamics

Instead of using $\mathbb{E}[V(s_i)]$ , we used $\max_{a’} Q_\phi(s_i’,a_i’)$ , the value function $V(s_i)$ is approxiamted by $\max_{a’} Q_\phi(s_i,a’)$ and intead of doing expectations on the future possible states, we used the next state in the sample $s_i’$

Works for off-policy samples

Only one network, no high-variance policy gradient

No convergence guarentees for non-linear function approximation (more on this later)

Special Cases of Fixed Q-Fitting

During exploration phase, using the greedy algorithm may not be the optimal choice (we want to maximize entropy!)

“Epsilon Greedy”

\pi(a_t|s_t)=\begin{cases} 1-\epsilon &\quad \text{if } a_t = \argmax_a Q_\phi(s_t,a_t) \\ \epsilon /(|A|-1) &\quad \text{otherwise} \end{cases}

“epsilon chance of exploring other options other than optimal action”

Common practice is to vary epsilon while training (early on(Q is bad), larger epsilon)

“Exponential”

\pi(a_t|s_t) \propto \exp(Q_\phi(s_t,a_t))

Best action will be most frequent, but leave some probability for exploration. And plus, if there is a second largest Q, then this second largest is considered more than other options.

Value Function Learning Theory

For tabular value iteration algorithm:

The Bellman Operator encaptures the logic of updating $V(s)$

And one fact is that:

$V^*$ , the value function for the optimal policy, is a fixed point of $B$

$V^*$ always exists, is always unique, and always corresponds to the optimal policy

Does fixed point iteration converge to $V^*$

We can prove that the value iteration reaches $V^*$ because $B$ is a contraction

Contraction means: for any $V$ and $\bar{V}$ , we have $||BV-B\bar{V}||_\infin \le \gamma||V-\bar{V}||_\infin$ where $\gamma \in (0,1)$

Meaning that $V$ and $\bar{V}$ will get closer and closer as we apply $B$ to them

If we replace $\bar{V}$ by $V^*$ (and since $BV^* = V^*$ ),

||BV-V^*||_\infin \le \gamma ||V-V^*||_\infin

For fitted value iteration algorithm:

Step 1 basically applies the bellman operator

We will define a new operator for step 2, $\Pi$ (pi)

Step 2 performs the following:

“Find an value function in the value function model hypothesis space $\Omega$ that optimizes the objective”

V' \leftarrow \argmin_{V' \in \Omega} \frac{1}{2} \sum ||V'(s)-(BV)(s)||^2

So step 2 performs this model fitting operator $\Pi$ that projects $BV$ onto hypothesis space $\Omega$ , our iteration algorithm can now be described as

V \leftarrow \Pi BV

$B$ is still a contraction with respect to $\infin$ norm

||BV-B\bar{V}||_\infin \le \gamma||V-\bar{V}||_\infin

$\Pi$ is a contraction wr.t. L2-norm

||\Pi V- \Pi \bar{V}||^2 \le ||V - \bar{V} ||^2

However, $\Pi B$ is not a contraction of any kind

So fitted value iteration does not converge in general and often does not converge in practice

Same with fitted Q-Iteration, Batch actor-critic

🧙🏽‍♂️

Bad theoretical properties, but works in practice lol

But why? Isn’t value function fitting just graident descent?

We can actually turn this into a gradient descent algorithm by computing into those target functions ⇒ resulting algorithm is called residual algorithms, has poor numerical properties & doesn’t work well in practice

Correlation Problem in Q-Learning

⚠️

Sequential States are Strongly Correlated And Target value is always changing (chasing its own tails)

Think about a sequence

In the early 3 steps, the target value is kind of “overfit” to those 3 values

In the supervised setting of learning Q / Value functions, the data points seen by the target values are only local states

We can solve this by adding more batches at one time (by synchronized parallel Q-learning or asynchronous parallel Q-learning)

Or we use replay buffers (Since fitted Q-Learning is basically a off-policy method) ⇒ Samples are no longer correlated and multiple samples in the batch (low-variance gradient)

But where does the data come from:

Need to periodically feed the replay buffer

⚠️

On full fitted Q-Iteration algorithm, we set

\phi \leftarrow \argmin_{\phi} \frac{1}{2} \sum_i ||Q_\phi(s_i,a_i)-y_i||^2

But do we want it to actually converge to argmin if the sample has high variance?

Maybe just move one gradient step instead

\phi \leftarrow \phi - \alpha \sum_i \frac{dQ_\phi}{d\phi}(s_i,a_i)(Q_\phi(s_i,a_i)-y_i)

Usually ⇒ $K \in [1, 4]$ , $N \in [10000, 50000]$

Target network makes sure that we’re not trying to hit a moving target ⇒ and now it looks more like supervised regression

🔥

Popular Alternative of target network update:

\phi ' \leftarrow \tau \phi ' + (1-\tau) \phi

\tau = 0.999

works well

Question: Chasing its tail relationship, is there a typical scenerio where Q function chases its tail and shows bad behaviors?

Classic Deep Q-Learning Algorithm (DQN)

A special case(with specific parameters) of Q-learning with replay buffer and target network

A general view of Q-Learning

Online Q-learning (last lecture): evict immediately, process 1, process 2, and process 3 all run at the same speed.

DQN: Process 1 and process 3 run at the same speed, process 2 is slow.

Fitted Q-iteration: process 3 in the inner loop of process 2, which is in the inner loop of process 1

Overestimation in Q-Learning and Double Q-Learning

Q functions are not accurate (much much larger)

🔥

Why does Q-function think that it’s gonna get systematically larger values than true values.

Because target value

y_j = r_j + \gamma \underbrace{\max_{a_j '}}_{\mathclap{\text{this last term is the problem}}} Q_{\phi '}(s_j ', a_j ')

Imagine two r.v. $X_1, X_2$

We can prove:

\mathbb{E}[\max(X_1,X_2)] \ge \max(\mathbb{E}[X_1],\mathbb{E}[X_2])

But:

$Q_{\phi '}(s',a')$ is not perfect, it is “noisy” ⇒ We are always selecting the positive errors while training using the $\max$

Note that

\max_{a'}Q_{\phi '}(s',a')=Q_{\phi '}(s',\underbrace{\argmax_{a'} Q_{\phi '}(s',a')}_{\mathclap{\text{action selected according to $Q_{\phi '}$}}})

So use “double Q-Learning” ⇒ use two networks

Update $\phi A$ by using $\phi B$ as a target network and $\phi A$ as an action selector, opposite with $\phi B$ update.

Q_{\phi A}(s,a) \leftarrow r+\gamma Q_{\phi B}(s',\argmax_{a'} Q_{\phi A}(s',a'))

Q_{\phi B}(s,a) \leftarrow r + \gamma Q_{\phi A}(s', \argmax_{a'} Q_{\phi B}(s',a')

Intuition: Choosing the “optimal” (but due to noise) action in $Q_{\phi A}$ will cause the noise of the same action in $Q_{\phi B}$ to be added into the result, therefore the “overestimation” effect is mitigated

In practice, instead of having two Q functions, use the two Q functions that we already have.

We already have $\phi$ and $\phi '$

In standard Q-learning:

y = r+\gamma Q_{\phi '}(s', \argmax_{a'} Q_{\phi '}(s',a'))

Double Q-Learning:

y = r+\gamma Q_{\phi '}(s',\argmax_{a'} Q_{\phi}(s',a'))

Multi-step returns

Q-learning target

y_{j,t} = r_{j,t} + \gamma \max_{a_{j,t+1}} Q_{\phi '}(s_{j,t+1},a_{j,t+1})

Early on in training, the term $\gamma \max_{a_j, t+1} Q_{\phi ‘}(s_{j,t+1},a_{j,t+1})$ only gives us random noise if the network is bad, so $r_{j,t}$ is the most important. But later in training, when $Q_{\phi'}$ gets better and better, this term dominates(since we have more terms then just a single term reward) and is more important.

So we can have something like “Monte Carle” sum of rewards in Actor-Critic algorithms

y_{j,t} = \sum_{t' =t}^{t+N-1} \gamma^{t'-t}r_{j,t'} + \gamma^N \max_{a_{j,t+N}}({s_{j,t+N},a_{j,t+N})}

Higher variance

but lower bias
1. Faster learning especially early on

but only correct when on-policy learning
1. In the second step it actually matters what action you take because the exploration policy might be different from current policy

How to fix the “on-policy” limit?

Ignore the problem (😂 Yeah this is SOOOO CS)
1. Often works very well

Cut the trace
1. dynamically choose N to get only on-policy data
1. Works well when data mostly on-policy, and action space is small

Importance sampling
1. “Safe and efficient off-policy reinforcement learning. “ Munos et al. ‘16

Extending Q-Learning to continuous action space

Problem with continuous actions:

Our policy has to select $\argmax Q_\phi$

When evaluting the $y_j$ for training $Q_\phi$ we also need to $\argmax$
1. Particularly problematic(since this runs in a loop!）

Options:

Continuous Optimization Procedure
1. Gradient based optimization (like SGD) is a bit slow in the inner loop
1. Action space typically low-dimensional ⇒ So no need to do gradient optimization

Stochastic optimization
1. Uses the fact that action space is low-dimensional (easy to solve for optima)

Use a function class that is easy to optimize
1. Quadratic function?
  1. Gu, Lillicrap, Sutskever, L., ICML 2016
    1. Normalized Advantage Functions (NAF) architecture
1. No change to algorithm
1. Just as efficient as Q-Learning
1. But loses representational power

Learn an approximate maximizer
1. Learn a function maximizer using neural nets
1. DDPG (Lillicrap et al. ICLR 2016)
  1. “Deterministic” actor-critic (really approximate Q-Learning)
  1. $\max_{a} Q_{\phi} (s,a) = Q_\phi (s, \argmax_a Q_\phi (s,a))$
    1. Idea is to train another network $\mu_\theta(s)$ such that $\mu_\theta(s) \approx \argmax_a Q_{\phi}(s,a)$
    1. $\frac{dQ_\phi}{d\theta} = \frac{da}{d\theta} \frac{d Q_{\theta}}{da}$
1. classic: NFQCA
1. recent: TD3 and SAC

Stochastic Optimization

Simple Solution

\max_{a} Q(s,a) \approx \max \{ Q(s,a_1), \dots, Q(s,a_N) \}

Where $(a_1, \dots, a_N)$ are sampled from some distribution (e.g. uniform)

Dead simple

Efficiently parallelizable

But - not very accurate

More accurate (works OK for ≥ 40 dims):

Cross-entropy method (CEM)
1. simple iterative stochastic optimization
1. sampling actions from distribution like in the simple method but then refines to a range and then continues to sample in a smaller and smaller range

CMA-ES
1. substantially less simple iterative stochastic optimization

Implementation Tips

Huber loss (interpolating between squared error and absolute value loss)

Q-learning takes some care to stabilize
1. Test on easy, reliable tasks first, make sure the implementation is correct
1. Large replay buffers help improve stability
  1. Looks more like fitted Q-iteration
1. Takes time, be patient - might be no better than random for a while
1. Start with high exploration (epsilon) and gradually reduce
1. Bellman error gradients can be big; clip gradients or use Huber loss

Double Q-learning helps a lot in practice
1. Simple & no downsides!

N-step returns also help a lot
1. but have some downsides (will systematically bias the objective)

Schedule exploration (high to low) and learning rates (high to low), Adam optimizer can help too

Run multiple random seeds, its very inconsistent between runs

Model-based Methods

🔥

Why Model-based methods? Because if we know the transition function

f(s_t, a_t) = \mathbb{P}_{(s_{t+1}|s_t,a_t)}

then we can use trajectory planning ⇒ So we can learn

f(s_t,a_t)

from data

📌

Model-based RL can be prone to error in distribution mismatch ⇒ very like behavior cloning because when planned trajectory queries out-of-sample states, then

f(\cdot)

is likely to be wrong

NPC

Performance Gap Issue

We want good exploration to gather more data to address the distribution shift, but with a not-so-good early model we cannot deploy good exploration techniques

Basically the model early on overfits an function approximator and the exploration policy is stuck on a local minima / maxima

Uncertainty Estimation

Uncertainty estimation helps us reduce performance gap.

Under this trick, the expectation of reward under high-variance prediction is very low, even though the mean is the same

However:

We still need exploration to get better model

Expected value is not the same as pessimistic value

But how to build it?

Use NN?
1. Cannot express uncertainty of unseen data accurately ⇒ when querying out-of-sample data, the uncertainty output is arbitrary
1. “The model is certain about data, but we are not certain about the model”

Estimate Model Uncertainty
1. Estimate $\argmax_\theta \log \mathbb{P}(\theta|D) = \argmax_\theta \log \mathbb{P}(D|\theta)$
1. Can we instead estimate the distribution $\mathbb{P}(\theta|D)$ ?
  1. We can use this to get a posterior distribution over the next state
    1. $\int p(s_{t+1}|s_t,a_t,\theta) p(\theta|D) d\theta$
  1. Bayesian Neural Nets
    1. Every weight, instead of being a number, is a distribution
    1. But it’s difficult to join parameters into a single distribution
    1. So we do approximation
      1. $p(\theta|D) = \prod_i p(\theta_i|D)$
        Very Crude approximation
      1. $p(\theta_i|D) = N(\mu_i, \sigma_i^2)$
        Instead of learning numerical value learn mean value and std/variance
      1. Bllundell et al. Weight Uncertainty in Neural Networks
      1. Gal et al. Concrete Dropout

Bootstrap Ensembles
1. Train several different neural nets and bootstrap samples( $D_i$ sample with replacement from $D$ ) to feed to those networks
  1. So each network learns slightly differently
  1. In theory each NN learns well on their own training data but makes different mistakes outside of training data
1. Then estimate $p(\theta|D) \approx \frac{1}{N} \sum_i \delta(\theta_i)$
1. $\int p(s_{t+1}|s_t,a_t,\theta) p(\theta|D) d\theta \approx \frac{1}{N} \sum_i p(s_{t+1}|s_t,a_t,\theta_i)$
1. Very crude approximation
  1. Because the number of models is usually small(expensive)
  1. But works
  1. Resampling with replacement is usually unnecessary, because SGD and random initialization usually makes the models sufficiently independent

With Complex Observations (images)

High dimensionality with observation prediction model
1. Redundancy

Partial Observability

Can we seperately learn $p(o_t | s_t)$ , which is high-dim but not dynamic, and $p(s_{t+1}|s_t,a_t)$ , which is low-dim but dynamic?

Now we need to maximize

\max_\phi \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \mathbb{E}[\log p_\phi(s_{t+1}|s_{t,i},a_{t,i}) + \log p_\phi (o_{t,i}|s_{t,i})]

Note that the expectation is conditioned on

(s_t,s_{t+1}) \sim p(s_t,s_{t+1}|o_{1:T},a_{1:T})

So can we learn an additional approximate posterior (encoder):

q_\psi (s_t|o_{1:t},a_{1:t})

Also we have other choices:

$q_\psi(s_t,s_{t+1}|o_{1:T},a_{1:T})$ - full smoothing posterior
1. most accurate
1. most complicated to train
1. Preferred when the state is less fully-observed

$q_\psi (s_t | o_t)$
1. single-step encoder
1. simplest but less accurate
1. stochastic case requires variational inference
1. Deterministic: $q_\psi(s_t|o_t) = \delta(s_t = g_\psi(o_t))$

To use uncertainty

Before uncertainty is introduced, we have (assuming $s_{t+1} = f(s_t,a_t)$

J(a_1,\dots,a_H) = \sum_{t=1}^H r(s_t,a_t)

Now(With bootstrap):

J(a_1,\dots,a_H) = \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^H r(s_{t,i},a_i)

Other options:

Moment matching

more complex posterior estimation with BNNs

Can we just backprop through policy / dynamics model?

📌

Generally No!

Similar parameter sensitivity problems as shooting methods
1. But no longer have convenient second order LQR-like method, because policy parameters couple all the time steps

Similar problems to training long RNNs with BPTT
1. Vanishing and exploding gradients

Let’s compare policy gradient:

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta(a_{i,t}|s_{i,t})\hat{Q}_{i,t}^\pi

with backprop (pathwise) gradient:

\nabla_\theta J(\theta) = \sum_{t=1}^T \frac{\partial a_t}{\partial \theta} \frac{\partial s_{t+1}}{\partial a_t}(\sum_{t'=t+1}^T \frac{\partial r_{t'}}{\partial s_{t'}}(\prod_{t'' = t+2}^{t'} \frac{\partial s_{t''}}{\partial a_{t''-1}}\frac{\partial a_{t''-1}}{\partial s_{t''-1}}+\frac{\partial s_{t''}}{\partial s_{t''-1}}))

Policy gradient might be more stable (if enough samples are used) because it does not require multiplying many Jacobians

Parmass et al. “18: PIPP: Flexible Model-Based Policy Search Robust to the Curse of Chaos”

It we use policy gradient to backprop through our model dynamics model, there would still be a problem (although generating samples does not require interacting with physical world or simulator)

Left: Open-loop planning with long rollouts; Middle: Open-loop planning with shorter rollouts; Right: Collect real-world data from current policy and do short rollouts planning with data sampled from real distribution

But this does not solve the problem because the point of using model-based RL is being sample efficient and using sampled real world data and do short-rollout open-loop planning restrict how much we can change our policy.

Model-based RL with Policies

📌

Question is how to use the model’s predictions? fit Q functions or Value functions or what?

Model-Based Acceleration (MBA)
1. Gu et al. Continuous deep Q-learning with model-based acceleration. ‘16

Model-Based Value Expansion (MVE)
1. Feinberg et al. Model-based value expansion. ’18

Model-Based Policy Optimization (MBPO)
1. Janner et al. When to trust your model: model-based policy optimization. ‘19

Good Idea:

Sample Efficient

Bad Idea:

Additional Source of bias if model is not correct
1. Reduce this by using ensemble methods

If not seen states before then we still cannot perform valid action

Multi-step Models and Successor Representations

📌

The job of the model is to evaluate the policy

\begin{split} V^\pi(s_t) &= \sum_{t=t'}^\infin \gamma^{t'-t} \mathbb{E}_{p(s_{t'}|s_t} \mathbb{E}_{a_{t'}|s_{t'})}[r(s_{t'},a_{t'})] \\ &= \sum_{t=t'}^\infin \gamma^{t' - t} \mathbb{E}_{p(s_{t'}|s_t)}[r(s_{t'})] \\ &= \sum_{t = t'}^\infin \gamma^{t'-t} \sum_s p(s_{t'} = s|s_t)r(s) \\ &= \sum_s \underbrace{(\sum_{t=t'}^\infin \gamma^{t' - t} p(s_{t'} = s | s_t))}_{\mathclap{\text{Add $(1-\gamma)$ term to the front makes it $p_\pi(s_{future}=s|s_t)$}}} r(s) \end{split}

p_\pi(s_{future}=s|s_t) = (1-\gamma)\sum_{t=t'}^\infin \gamma^{t' - t} p(s_{t'} = s | s_t)

Therefore

V^\pi(s_t) = \frac{1}{1-\gamma} \underbrace{\sum_s p_\pi(s_{future}=s|s_t) r(s)}_{\mathclap{\mu^\pi(s_t)^\top \vec{r}}}

Where

\mu_i^\pi = p_\pi(s_{future} = s_i|s_t)

is the “successor representation”

Dayan Improving Generalization for Temporal Difference Learning: The Successor Representation, 1993.

\begin{split} \mu_i^\pi(s_t) &= (1-\gamma) \sum_{t'=t}^\infin \gamma^{t'-t} p(s_{t'} = i | s_t) \\ &= (1-\gamma)\delta(s_t = i) + \gamma \mathbb{E}_{a_t \sim \pi(a_t|s_t), s_{t+1} \sim p(s_{t+1}|s_t,a_t)}[\mu_i^\pi(s_{t+1}] \end{split}

Hmm…looks like a bellman backup with “reward” $r(s_t) = 1-\gamma \delta(s_t = i)$

But issues:

Not clear if learning successor representation is easier than model-free RL

how to scale to large state spaces?

How to extend to continuous state spaces?

To scale to large state spaces, use successor feature of $s_t$

\psi_j^\pi(s_t) = \sum_s \mu_s^\pi(s_t)\phi_j(s) = \mu_\pi(s_t)^\top \vec{\phi}_j

If we can express the reward function as combination of features of state s

r(s) = \sum_j \phi_j(s) w_j = \phi(s)^\top w

Turns out we can express the value function as

V^\pi(s_t) = \psi^\pi(s_t)^\top w = \sum_j \mu^\pi(s_t)^\top \vec{\phi}_j w = \mu^\pi(s_t)^\top \sum_j \vec{\phi}_j w = \mu^\pi(s_t)^\top \vec{r}

The dimensionality of $\phi$ and $\psi$ would be a lot lower than the dimension of possible states

Can also construct a Q-function like version

\psi_j^\pi(s_t,a_t) = \phi_j(s_t) + \gamma \mathbb{E}_{s_{t+1} \sim p(s_{t+1}|s_t,a_t), a_{t+1} \sim \pi(a_{t+1}|s_{t+1})}[\psi_j^\pi(s_{t+1},a_{t+1})]

Q^\pi(s_t,a_t) \approx \psi^\pi(s_t,a_t)^\top w

(when $r(s) = \phi(s)^\top w$ )

Using Successor Features

Recover a Q-function very quickly
1. Train $\psi^\pi(s_t,a_t)$ via Bellman backups
1. Get some reward samples $\{s_i, r_i \}$
1. Get $w \leftarrow \argmin_w \sum_i ||\phi(s_i)^\top w - r_i||^2$
1. Recover $Q^\pi(s_t,a_t) \approx \psi^\pi(s_t,a_t)^\top w$
  1. $\pi’(s) = \argmax_a \psi^\pi(s,a)^\top w$
    1. This is only equivalent to one step of policy iteration because Q is with respect to the actor

Recover many Q-function
1. Train $\psi^{\pi_k}(s_t,a_t)$ for many policies $\pi_k$ via Bellman backups
1. Get some reward samples $\{s_i, r_i \}$
1. Get $w \leftarrow \argmin_w \sum_i ||\phi(s_i)^\top w - r_i||^2$
1. Recover $Q^{\pi_k}(s_t,a_t) \approx \psi^{\pi_k}(s_t,a_t)^\top w$ for every $\pi_k$
  1. $\pi’(s) = \argmax_a \max_k \psi^{\pi_k}(s,a)^\top w$
    1. This is only equivalent to one step of policy iteration because Q is with respect to the actor
    1. Finding to highest reward policy in each state

Continuous Successor Representations (C-Learning)

🧙🏽‍♂️

So can we just frame successor representation as classification?

p^\pi(\underbrace{F=1}_{\mathclap{\text{means $s_{future}$ is a future state under $\pi$}}}|s_t,a_t,s_{future}) = \frac{p^\pi(s_{future}|s_t,a_t)}{p^\pi(s_{future}|s_t,a_t)+p^\pi(s_{future})}

Positive set during training:

D_+ \sim p^\pi(s_{future}|s_t,a_t)

Negative set just pulled randomly.

To train (On-policy algorithm, can also derive an off-policy algorithm that is also very efficient):

Sample $s\sim p^\pi(s)$ ⇒ run policy, sample from trajectories

Sample $s \sim p^\pi(s_{future}|s_t,a_t)$ ⇒ pick positive future pairs

Update $p^\pi(F=1|s_t,a_t,s)$ using SGD with cross entropy loss

Eysenbach, Salakhutdinov, Levine. C-Learning: Learning to Achieve Goals via Recursive Classification. 2020.

Exploration (Lec 13)

It’s hard for algorithms to know what rules of the environment are “Mao” Game

The only rule you may be told is this one
1. Incur a penalty when you break a rule
1. Can only discover rules through trial and error
1. Rules don’t always make sense to you

So here is the definition of exploration problem:

How can an agent discover high-reward strategies that require a temporally extended sequence of complex behaviors that, individually, are not rewarding?

How can an agent decide whether to attempt new behaviors or continue to do best things it knows so far?

So can we derive an optimal exploration strategy:

Tractable(易于理解) - If it is easy to know that the policy is optimal or not

Multi-arm bandits (1-step, stateless RL) / Contextual bandits (1 step, but there’s a state)
1. Can formalize exploration as POMDP(Partial-observed MDP because although there’s only one time, performing actions help us expand our knowledge) identification
1. policy learning is trivial even with POMDP

small, finite MDPs
1. Can frame as Bayesian model identification, reason explicitly about value of information

Large or infinite MDPs
1. Optimal methods don’t work
  1. Exploring with random actions: oscillate back and forth, might not go to a coherent or interesting place
1. But can take inspiration from optimal methods in smaller settings
1. use hacks

Bandits

The dropsophila(黑腹果蝇, 模式生物) of exploration problems

Multi-arm bandit ⇒ have to make decision on which machine to play; Pulling one of the arms doesn’t mean it’s a bad decision

So the definition of the bandit:

Assume $r(a_i) \sim p_{\theta_i}(r_i)$

e.g. $p(r_i = 1) = \theta_i$ and $p(r_i = 0) = 1 - \theta_i$

Where (but you don’t know):

\theta_i \sim p(\theta)

This defines a POMDP with $s = [\theta_1, \dots, \theta_n]$

Belief state is $\hat{p}(\theta_1, \dots, \theta_n)$

Solving the POMDP yields the optimal exploration strategy

But this is an overkill - belief state is huge! ⇒ we can do very well with much simpler strategies

We will define regret as the difference from optimal policy at time step $T$

Reg(T) = T\mathbb{E}[r(a^*)] - \sum_{t=1}^T r(a_t)

How do we beat bandit?

Variety of relatively simple strategies

Often can provide theoretical guarantees on regret
1. Empirical performance may vary

Exploration strategies for more complex MDP domains will be inmspired by those strategies

Optimistic exploration $Reg(T) \in O(\log T)$

Keep track of average reward $\hat{\mu}_a$ for each action a

Exploitation: pick $a = \argmax \hat{\mu}_a$

Optimistic Estimate: $a = \argmax \hat{\mu}_a + C \sigma_a$
1. “Try each arm until you are sure it’s not great”
1. $a = \argmax \hat{\mu}_a + \sqrt{\frac{2 \ln T}{N(a)}}$ where $N(a)$ is number of times we have picked this action

To put this in practice, use $r^+(s,a) = r(s,a) + B(N(s))$ ⇒ easy to add in but hard to tune the weights of $B(N(s))$ .

Problem is in continuous states ⇒ we never see same thing twice ⇒ but some states are more similar than others

Beliemare et al. “Unifying Count-based Exploration …”

So we will

Fit a density model $p_\theta(s)$ or $p_\theta(s,a)$

$p_\theta(s)$ might be high even for a new $s$ if $s$ is similar to previous seen states

But how can the distribution of $p_\theta$ match the distribution of a count?

Notice that the true probability is $P(s) = \frac{N(s)}{n}$ , and after seeing $s$ , $P’(s) = \frac{N(s) + 1}{n+1}$

How to get to $\hat{N}(s)$ ?

p_\theta(s_i) = \frac{\hat{N}(s_i)}{\hat{n}}, p_{\theta}'(s_i) = \frac{\hat{N}(s_i)+1}{\hat{n}+1}

Solving the equation, we find

\hat{N}(s_i) = \hat{n}p_\theta(s_i), \hat{n} = \frac{1 - p_\theta'(s_i)}{p_\theta'(s_i)-p_\theta(s_i)} p_\theta(s_i)

Different classes of bonuses:

UCB bonus $B(N(s)) = \sqrt{\frac{2 \ln n}{N(s)}}$

MBIE-EB (Strehl & Littman, 2008): $B(N(s)) = \sqrt{\frac{1}{N(s)}}$

BEB (Kolter & Ng, 2009): $B(N(s)) = \frac{1}{N(s)}$

So we need to output densities, but doesn’t necessarily need to produce great samples

Opposite considerations from many popular generative models like GANs

Bellemare et al. “CTS” Model: Condition each pixel on its top-left neighborhood

Other models: Stochastic neural networks, compression length, EX2

Probability Matching / Posterior Sampling (Thompson Sampling)

Assume $r(a_i) \sim p_{\theta_i} (r_i)$ ⇒ which defines a POMDP with $s = [\theta_1, \dots, \theta_n]$

Belief state is $\hat{p}(\theta_1, \dots, \theta_n)$

Idea:

Sample $\theta_1, \dots, \theta_n \sim \hat{p}(\theta_1, \dots, \theta_n)$

Pretend the model $\theta_1, \dots, \theta_n$ is correct

Take the optimal action

Update the model

Chapelle & Li, “An Empirical Evaluation of Thompson Sampling.”

⇒ Hard to analyze theoretically but can work very well empirically

Osband et al. “Deep Exploration via Boostrapped DQN”

What do we sample?

how do we represent the distribution?

Bootstrap ensembles:

Given a dataset $D$ , resample with replacement $N$ times to get $D_1, \dots, D_N$

train each model $f_{\theta_i}$ on $D_i$

To sample from $p(\theta)$ , sample $i \in [1, \dots, N]$ and use $f_{\theta_i}$

❓

Train

N

big neural nets is expensive, can we avoid it? In the paper they trained a net with different heads ⇒ this may actually be undesirable since now the outputs are correlated but they may be uncorrelated enough for us to use

🧙🏽‍♂️

This might help better than epsilon-greedy because instead of maybe oscillating back adn forth (and not go somewhere intersting at all), we are commited to a randomized but internally consistant strategy for an entire episode

No change to original reward function

Very good bonuses often do better than this

Methods that use Information Gain

Bayesian Experimental Design

If we want to determine some latent variable $z$ ⇒ $z$ might be optimal action or its value

Which action do we take?

Let $H(\hat{p}(z))$ be the current entropy of our $z$ estimate

Let $H(\hat{p}(z)|y)$ be the entropy of our $z$ estimate after observation $y$ ( $y$ might be $r(a)$ in the case of RL)

The lower the entropy, the more precisely we know $z$

IG(z,y) = \mathbb{E}_y [H(\hat{p}(z)) - H(\hat{p}(z)|y)]

Typically depends on action, so we will use the notion $IG(z, y|a) = \mathbb{E}_y [H(\hat{p}(z) - H(\hat{p}(z)|y)|a)]$

🧙🏽‍♂️

One important thing to find is decide what

y

is in our problem and what

z

Russo & Van Roy “Learning to Optimize via Information-Directed Sampling”

y = r_a, z = \theta_a

Observe reward and learn parameters of $\hat{p}(r_a)$

g(a) = IG(\theta_a, r_a|a) \rightarrow \text{information gain of $a$}

\Delta(a) = \mathbb{E}[r(a^*) - r(a)] \rightarrow \text{expected suboptimality of $a$}

We want to gain more information but we don’t want our policy to be suboptimal

So we will choose $a$ according to

\argmin_a \frac{\Delta(a)^2}{g(a)}

Houthooft et al. “VIME”

Question:

Information gain about what?
1. Reward $r(s,a)$
  1. Not useful is reward is sparse
1. State density $p(s)$
  1. A bit strange, but somewhat makes sense!
1. Dynamics $p(s’|s,a)$
  1. Good proxy for learning the MDP, though still heuristic

Generally they are intractable to use exactly, regardless of what is being estimated

A few approximations:

Prediction Gain (Schmidhuber ‘91, Bellemare ‘16)
1. $\log p_{\theta}’ (s) - \log p_\theta(s)$
1. If density changed a lot, then the state is novel

Variational Inference (Houthooft et al. “VIME”)
1. IG can be equivalently written as $D_{KL}(p(z|y), p(z))$
1. Learn about transitions $p_\theta(s_{t+1}|s_t,a_t): z = \theta$
1. $y = (s_t, a_t, s_{t+1})$
1. Intuition: a transition is more informative if it causes belief over $\theta$ to change
1. Idea:
  1. Use variational inference to estimate $q(\theta|\phi) \approx p(\theta|h)$
    1. Specifically optimize variational lower bound $D_{KL}(q(\theta|\phi), p(h|\theta) p(\theta))$
    1. Represent $q(\theta|\phi)$ as product of independent Gaussian parameter distributions with mean $\phi$
      1. $p(\theta|D) = \prod_i p(\theta_i |D)$
      1. $p(\theta_i|D) = N(\underbrace{\mu_i, \sigma_i^2}_{\mathclap{\phi}})$
    1. See Blundell et al. “Weight uncertainty in neural networks
  1. Given new transition $(s,a,s’)$ , update $\phi$ to get $\phi'$
  1. use $D_{KL}(q(\theta|\phi’), q(\theta|\phi))$ as approximate bonus

Appealing mathematical formalism

Models are more complex, generally harder to use effectively

Counting with Hashes

What if we still count states, but compress them into hashes and count them

Compress $s$ into k-bit code via $\phi(s)$ then count $N(\phi(s))$

shorter codes = more hash collisions

similar states get the same hash? Maybe
1. Depends on model we choose
1. We can use an autoencoder and this improve the odds of doing this

Tang et al. “#Exploration: A Study of Count-Based Exploration”

Implicit Density Modeling with Exemplar Models

Fu et al. “EX2: Exploration with Exemplar Models…”

We ned $p_\theta(s)$ to be able to output densities, but doesn’t necessarily need to produce great samples ⇒ can we explicitly compare the new state to past states?

🧙🏽‍♂️

Intuition: The state is novel if it is easy to distinguish from all previous seen states by a classifier

For each observed state $s$ , fit a classifier to classify that state against all past states $D$ and use classifier error to obtain density

p_\theta(s) = \frac{1-D_s(s)}{D_s(s)}

where $D_s(s)$ is the probability that the classifier assigns $s$ as a “positive”

In reality, every state is unique so we regularize the classifier

Heuristic estimation of counts via errors

We just need to tell if state is novel or not

Given buffer $D = \{(s_i,a_i)\}$ , fit $\hat{f}_\theta(s,a)$

So we basically use the error of $\hat{f}_\theta(s,a)$ and actual $f^*(s,a)$ as a bonus

\epsilon(s,a) = ||\hat{f}_\theta(s,a)-f^*(s,a)||^2

But what function should we use for $f^*$ ?

$f^*(s,a) = s’$

$f^*(s,a)$ as a neural network, but with parameters chosen randomly

We mentioned about how $D_{KL}(q(\theta|\phi’), q(\theta|\phi))$ can be seen as Information Gain, it can also be viewed as change in network parameters $\phi$

So if we forget about IG, there are many other ways to measure this

Stadie et al. 2015:

encode image observations using auto-encoder

build predictive model on auto-encoder latent states

use model error as exploration bonus

Schmidhuber et al. (see, e.g. “Formal Theory of Creativity, Fun, and Intrinsic Motivation):

exploration bonus for model error

exploration bonus for model gradient

many other variations

Unsupervised learning of diverse behaviors

What if we want to recover diverse behavior without any reward function at all?

Learn skills without supervision
- But then use them to accomplish goals

Learn sub-skills to use with hierarchical reinforcement learning

Explore the space of possible behaviors

One possible case is to describe a target goal and the machine would just try to reach the goal

Nair*, Pong*, Bahl, Dalal, Lin, L. Visual Reinforcement Learning with Imagined Goals. ’18 Dalal*, Pong*, Lin*, Nair, Bahl, Levine. Skew-Fit: State-Covering Self-Supervised Reinforcement Learning. ‘19

$\bar{x}$ may not be equal to $x_g$ at all…but we will do some updates regardless.

$p_\theta(x|z)$ ⇒ Latent Model (VAE) that transforms a proposed state $z$ to $x$

However: This means the model tends to generate states that we’ve already seen (since we sample from $p(z)$ ⇒ and we are not exploring very well

❓

How do we reach diverse goals?

We will modify step 4 ⇒ instead of doing MLE: $\theta, \phi \leftarrow \argmax_{\theta, \phi} \mathbb{E}[\log p(\bar{x})]$ , we will do a weighted MLE:

\theta,\phi \leftarrow \argmax_{\theta,\phi} \mathbb{E}[w(\bar{x}) \log p(\bar{x})]

We want to assign a greater weight to rarely seen actions, and since we’ve used a generator for $p_\theta(x|z)$ , we can use

w(\bar{x}) = p_\theta(\bar{x})^{\alpha}, \alpha \in [-1,0)

⇒ Note that for any $\alpha \in [-1,0)$ , the entropy $H(p_\theta(x))$ increases ⇒ proposing broader and broader goals

The RL formulation:

\max H(p(G))

$\pi(a|S,G)$ trained to reach goal $G$
1. as $\pi$ gets better, the final state $S$ gets close to $G$ ⇒ $p(G|S)$ becomes more deterministic

To maximize exploration,

\max H(p(G)) - H(p(G|S)) = \max I(S;G)

This is mainly for gathering data that leads to uniform density over the state distribution ⇒ doesn’t mean the policy is going randomly, what if we want a policy that goes randomly?

❓

But is state-entropy really a good objective?

Eysenbach’s Theorem: At test time, an adversary will choose the worst goal G ⇒ Then the best goal distribution use for training would be $p(G) = \argmax_p H(p(G))$ Hazan, Kakade, Singh, Van Soest. Provably Efficient Maximum Entropy Exploration

State Marginal Matching (SMM)

Learn $\pi(a|s)$ to minimize $D_{KL}(p_\pi(s), p^*(s))$

If we want to use intrinsic motivation, we have:

\tilde{r}(s) = \log p^*(s) - \log p_\pi(s)

Note that this reward objective sums to exactly the state-marginal objective above ⇒ However RL is not aware that $-\log p_\pi (s)$ depends on $\pi$ ⇒ tail chasing problem

We can prove that this $\pi^*(a|s)$ is a nash equilibrium for a two-player game

Learning Diverse Skills

\pi(a|s,\underbrace{z}_{\mathclap{\text{task index}}})

Reaching diverse goals is not the same as performing diverse tasks

not all behaviors can be captured by goal-reaching

\pi(a|s) = \argmax_{\pi} \sum_z \mathbb{E}_{s \sim \pi(s|z)} [r(s,z)]

We want reward states for other tasks $z’ \ne z$ to be unlikely, one way:

Use a classifier that gives you a softmax output of possibility of $z$ s

r(s,z) = \log p(z|s)

Connection to mutual information:

Eysenbach, Gupta, Ibarz, Levine. Diversity is All You Need. Gregor et al. Variational Intrinsic Control. 2016

I(z,s) = \underbrace{H(z)}_{\text{maximized by using uniform prior $p(z)$}} - \underbrace{H(z|s)}_{\text{minimized by maximizing $\log p(z|s)$}}

Offline RL (Batch RL / fully off-policy RL)

Huge gap in DL and DRL ⇒ supervised learning has tons of data!

Formally:

D = \{ (s_i,a_i,s_i',r_i) \} \\ s \sim d^{\pi_\beta}(s) \\ a \sim \pi_\beta(a|s) \\ r \leftarrow r(s,a)

$\pi_\beta$ is the unknown policy that collected the data

Off-Policy Evaluation (OPE)

Given $D$ , estimate return of some policy $J(\pi_\beta)$

Offline Reinforcement Learning

Given $D$ , learn the best possible policy $\pi_\theta$ (such that the evidence of the model is good is supported by the dataset)

How is this even possible?

Find the “good stuff” in a dataset full of good and bad behaviors

Generalization: Good behavior in one place may suggest good behavior in another place

“Stitching”: Parts of good behaviors (even badly-performed parts can have good behaviors) can be recombined

Bad intuition: It’s like imitation learning
- Though it can be shown to be provably better than imitation learning even with optimal data, under some structural assumptions ⇒ Kumar, Hong, Singh, Levine. Should I Run Offline Reinforcement Learning or Behavioral Cloning?

Better Intuition: Get order from chaos
- e.g. Get object from a drawer ⇒ Singh, Yu, Yang, Zhang, Kumar, Levine. COG: Connecting New Skills to Past Experience with Offline Reinforcement Learning.

What can go wrong if we just use off-policy RL (on data collected by other agents)?

Kalashnikov, Irpan, Pastor, Ibarz, Herzong, Jang, Quillen, Holly, Kalakrishnan, Vanhoucke, Levine. QT-Opt: Scalable Deep Reinforcement Learning of Vision-based Robotic Manipulation Skills

So it works in practice, but seems like a huge GAP between not-fine-tuned and fine-tuned result?

Kumar, Fu, Tucker, Levine. Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction. NeurIPS ‘19

Q-function overfitting with an off-policy actor-critic algorithm

Fundamental Problem: Counterfactual queries

Online RL algorithms don’t have to handle this because they can simply try this action and see what happens ⇒ not possible for offline policies

Offline RL methods must somehow account for these unseen (”out-of-distribution”) actions, ideally in a safe way

Distribution Shift

In a supervised learning setting, we want to perform empirical risk minimization (ERM):

\theta \leftarrow \argmin_\theta \mathbb{E}_{x \sim p(x), y\sim p(y|x)} [(f_\theta(x)-y)^2]

Given some $x^*$

\mathbb{E}_{x \sim p(x), y\sim p(y|x)} [(f_\theta(x)-y)^2] \text{ is low(since distribution is same as training set)} \\ \mathbb{E}_{x \sim \bar{p}(x), y \sim p(y|x)} [(f_\theta(x)-y)^2] \text{ is generally not if $\bar{p}(x) \ne p(x)$}

Yes, neural nets generalize well ⇒ but is is well enough?

If we pick $x^* \leftarrow \argmax_x f_\theta(x)$

Blue curve is the fitted and the green is the actual

When we choose argmax we are probably including a huge positive noise!

Q-Learning Actor-Critic with Distribution Shift

Q-objective:

\min_{Q} \mathbb{E}_{(s,a) \sim \pi_\beta(s,a)}[(Q(s,a)-y(s,a))^2]

The function approximates:

Q(s,a) \leftarrow r(s,a) + \mathbb{E}_{a' \sim \pi_{new}}[Q(s',a')]

The distribution shift problem kicks in when

\pi_{new} \ne \pi_\beta

And even worse,

\pi_{new} = \argmax_\pi \mathbb{E}_{a \sim \pi(a|s)} [Q(s,a)]

Online RL Setting (Sample “optimal” and find error in our approximation)

Offline Setting (No way to find error in our approximation)

🧙🏽‍♂️

Existing Challenges with sampling error and function approximation error in standard RL become much more severe in offline RL

Batch RL via Important Sampling (Traditional Offline Algorithms)

Importance Sampling:

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \underbrace{\frac{\pi_\theta(\tau_i)}{\pi_\beta(\tau_i)}}_{\mathclap{\text{importance weight}}} \sum_{t=0}^T \nabla_\theta \gamma^t \log \pi_\theta(a_{t,i}|s_{t,i})\hat{Q}(s_{t,i},a_{t,i})

Where the importance weight, is exponential in T

\frac{\pi_\theta(\tau)}{\pi_\beta(\tau)} = \frac{p(s_1) \prod_t p(s_{t+1}|s_t,a_t)\pi_\theta(a_t|s_t)}{p(s_1)\prod_t p(s_{t+1}|s_t,a_t) \pi_\beta(a_t|s_t)} \in O(e^T)

Can we fix this?

\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=0}^T \underbrace{(\prod_{t'=0}^{t-1} \frac{\pi_\theta(a_{t',i}|s_{t',i})}{\pi_\beta(a_{t',i}|s_{t',i})})}_{\mathclap{\text{accounts for difference in probability of landing in $s_{t,i}$}}} \nabla_\theta \gamma^t \log \pi_\theta(a_{t,i}|s_{t,i}) \underbrace{(\prod_{t'=t}^T\frac{\pi_\theta(a_{t',i}|s_{t',i})}{\pi_\beta(a_{t',i}|s_{t',i})}) }_{\mathclap{\text{accounts for incorrect $\hat{Q}(s_{t,i},a_{t,i})$}}}\hat{Q}(s_{t,i},a_{t,i})

Classic Advanced Policy Gradient RL completely strips away the first product term ⇒ assuming that the new policy $\pi_\theta$ is not too far away from $\pi_\beta$

We can estimate

\hat{Q}(s_{t,i},a_{t,i}) = \mathbb{E}_{\pi_\theta}[\sum_{t'=t}^T \gamma^{t'-t} r_{t'}] \approx \sum_{t'=t}^T \gamma^{t'-t} r_{t',i}

We can simplify the portion (using the fact that future actions don’t affect current reward)

(\prod_{t'=t}^T\frac{\pi_\theta(a_{t',i}|s_{t',i})}{\pi_\beta(a_{t',i}|s_{t',i})})\hat{Q}(s_{t,i},a_{t,i}) = \sum_{t'=t}^T(\prod_{t''=t}^T\frac{\pi_\theta(a_{t'',i}|s_{t'',i})}{\pi_\beta(a_{t'',i}|s_{t'',i})})\hat{Q}(s_{t,i},a_{t,i}) \approx \sum_{t'=t}^T(\prod_{t''=t}^{t'}\frac{\pi_\theta(a_{t'',i}|s_{t'',i})}{\pi_\beta(a_{t'',i}|s_{t'',i})})\hat{Q}(s_{t',i},a_{t',i})

But this is still exponential in $T$

🧙🏽‍♂️

To avoid exponentially exploding importance weights, we must use value function estimation!

The Doubly Robust Estimator

Jiang, N. and Li, L. (2015). Doubly robust off-policy value evaluation for reinforcement learning

\begin{split} V^{\pi_\theta}(s_0) &\approx \sum_{t=0}^T (\prod_{t'=0}^t \frac{\pi_\theta(a_{t'}|s_{t'})}{\pi_\beta(a_{t'}|s_{t'})})\gamma^t r_t \\ &= \sum_{t=0}^T(\prod_{t'=0}^t \rho_{t'}) \gamma^t r_t \\ &= \rho_0 r_0 + \rho_0\gamma\rho_1r_1 + \rho_0\gamma \rho_1 \gamma \rho_2 r_2 + \dots \\ &=\rho_0(r_0 + \gamma(\rho_1(r_1+...))) \\ &=\bar{V}^T \end{split}

We notice a recursion relationship:

\bar{V}^{T+1-t} = \rho_t(r_t + \gamma \bar{V}^{T-t})

Bandit case of doubly robust estimation:

V_{DR}(s) = \hat{V}(s) + \rho(s,a)(r_{s,a} - \hat{Q}(s,a))

Doubly Robust Estimation:

\bar{V}_{DR}^{T+1-t} = \hat{V}(s_t) + \rho_t(r_t + \gamma \bar{V}_{DR}^{T-t} - \hat{Q}(s_t,a_t))

Marginalized Important Sampling

In previous times we were trying to do importance sampling on action distributions ⇒ but it’s actually possible to do it on state distributions

🧙🏽‍♂️

Instead of using

\prod_t \frac{\pi_\theta(a_t|s_t)}{\pi_\beta(a_t|s_t)}

, estimate

w(s,a) = \frac{d^{\pi_\theta}(s,a)}{d^{\pi_\beta}(s,a)}

How to determine $w(s,a)$ ?

Typically solve some kind of consistency condition

e.g. (Zhang et al. GenDICE)
- $d^{\pi_\beta}(s’,a’)w(s’,a’) = (1-\gamma) p_0 (s’) \pi_\theta(a’|s’) + \gamma \sum_{s,a} \pi_\theta(a’|s’) p(s’|s,a) d^{\pi_\beta}(s,a) w(s,a)$
- Probability of seeing $(s’,a’)$ is the probability of starting with $s’$ and executing $a’$ or do transitions and arrive at the state $s’$ and executing $a’$

Solving for $w(s,a)$ typically involves some fixed point problem

Batch RL via Linear Fitted Value Functions

How have people thought about it before?
- Extend existing ideas for approximate dynamic programming and Q-learning to offline setting
- Derive tractable solutions with simple (e.g., linear) function approximators
- Distribution Shift not a huge problem since value functions are relatively simple

How are people thinking about it now?
- Derive approximate solutions with highly expressive function approximators (e.g., deep nets)
- The primary challenge turns out to be distributional shift

Assume we have a feature matrix

\Phi \in \mathbb{R}^{|S| \times K}

where $|S|$ is the number of states, and $K$ is the number of features. Then in order to do model-based RL in feature space

Estimate the reward
1. $\Phi w_r \approx r$ ⇒ $w_r = (\Phi^{\top} \Phi)^{-1} \Phi^{\top} \vec{r}$

Estimate the transitions
1. $\Phi P_{\Phi} \approx P^{\pi} \Phi$
  1. $P_\Phi$ ⇒ estimated feature space transition matrix $\in \mathbb{R}^{K \times K}$
  1. $P_\phi = (\Phi^{\top} \Phi)^{-1} \Phi^{\top} P^{\pi} \Phi$
1. $P^\pi \in \mathbb{R}^{|S| \times |S|}$ ⇒ Real transition matrix (on states), dependent on the policy

Estimate the value function
1. $V^{\pi} \approx V_{\Phi}^\pi = \Phi w_V$
  1. Solving for $V^\pi$ in terms of $P^\pi$ and $r$ :
    1. $V^\pi = r + \gamma P^\Pi V^\pi$
    1. $(1-\gamma P^\pi) V^\pi = r$
    1. $V^\pi = (I - \gamma P^\pi)^{-1}r$
1. $w_V = (I - \gamma P_\Phi)^{-1} w_r = (\Phi^\top \Phi-\gamma \Phi^\top P^\pi \Phi)^{-1} \Phi^\top \vec{r}$ ⇒ Least-sqaures Temporal Difference (LSTD)
1. But we don’t know $P^\pi$
1. With samples introduced, we will change our feature matrix $\Phi \in \mathbb{R}^{|D| \times K}$
1. And now we are going to replace $P^\pi \Phi$ with $\Phi’$ such that each row of $\Phi’_i$ is feature at the next timestep $\Phi_i’ = \phi(s_i’)$
  1. However, if we change policy, we no longer have $P^\pi$
1. Also replace $\vec{r}_i = r(s_i,a_i)$
1. Everything else works exactly same, but only that we now have some sampling error

Improve the policy
1. $\pi’(s) \leftarrow Greedy(\Phi w_V)$

Least Squares Policy Iteration (LSPI)

🧙🏽‍♂️

Replace LSTD with LSTDQ - LSTD but for Q functions

w_Q = (\Phi^\top \Phi-\gamma \Phi^\top \underbrace{\Phi'}_{\mathclap{\Phi'_i = \phi(s_i',\pi(s_i'))}})^{-1} \Phi^\top \vec{r}

LSPI:

Compute $w_Q$ for $\pi_k$

$\pi_{k+1}(s) = \argmax_a \phi(s,a)w_Q$

Set $\Phi_i’ = \phi(s_i’, \pi_{k+1}(s_i’))$

Problem:

Does not solve the distribution shift problem (in step 2 of argmax)

Policy Constraints

Very old idea, generally only implement this would not work wella

Q \leftarrow r(s,a) + \mathbb{E}_{a' \sim \pi_{new}}[Q(s',a')]

\pi_{new}(a|s) = \argmax_\pi \mathbb{E}_{a \sim \pi(a|s)}[Q(s,a)] \text{ s.t. } D_{KL}(\pi,\pi_\beta) \le \epsilon

$D_{KL}(\pi, \pi_\beta)$

Easy to implement

But not necessarily what we want

So maybe instead we want to pose a “support constraint”

\pi(a|s) \ge 0 \text{ iff } \pi_\beta(a|s) \ge \epsilon

Can approximate with Maximum Mean Discrepancy (MMD)

significantly more complex to implement

much closer to what we want

How to implement?

Implementing Implicit Policy Constraint in practice

Modify the actor objective
1. Common objective $\theta \leftarrow \argmax_\theta \mathbb{E}_{s \sim D} [\mathbb{E}_{a \sim \pi_\theta(a|s)}[Q(s,a)]]$
1. $D_{KL}(\pi, \pi_\beta) = \mathbb{E}[\log \pi(a|s) - \log \pi_\beta (a|s)] = -\mathbb{E}_\pi[\log \pi_\beta(a|s)] - H(\pi)$
1. So we can incorporate the KL divergence into the actor objective
1. Use Lagrange Multiplier
  1. $\theta \leftarrow \argmax_\theta \mathbb{E}_{s \sim D} [\mathbb{E}_{a \sim \pi_\theta(a|s)}[Q(s,a) + \lambda \log \pi_\beta (a|s)]+\lambda H(\pi (a|s))]$
  1. In practice we either solve the lagrange multiplier or treat it as hyper-parameter and tune it

Modify the reward funciton
1. $\bar{r}(s,a) = r(s,a) - D(\pi, \pi_\beta)$
1. Simple modification to directly penalize divergence
1. Also accounts for future divergence (in later steps)
1. Wu, Tucker, Nachum, Behavior Regularized Offline Reinforcement Learning. ‘19

Implicit Policy Constraint Methods
1. Solve for lagrangian condition of the KL constrained problem (straightforward to show via duality), we have
1. $\pi^*(a|s) = \frac{1}{Z(s)} \pi_\beta (a|s) \exp(\frac{1}{\lambda} A^\pi (s,a))$
1. Peters et al. (REPS)
1. Rawlik et al. (”psi-learning”)
1. We can do this by
  1. Approximate via weighted max likelihood
  1. $\pi_{new}(a|s) = \argmax_{\pi} \mathbb{E}_{\underbrace{(s,a) \sim \pi_\beta}_{(s,a) \sim D}} [\log \pi(a|s) \underbrace{\frac{1}{Z(s)} \exp(\frac{1}{\lambda} A^{\pi_{old}} (s,a)) }_{w(s,a)}]$
  1. Imitating good actions “more”(determined by $w(s,a)$ ) than bad actions
1. Problem: In order to get advantage values / target values we still need to query OOD actions
  1. If we choose $\lambda$ correctly the constraints will be respected at convergence, but not necessarily at intermediate steps

🧙🏽‍♂️

Can we avoid ALL OOD actions in the Q update?

Instead of doing

Q(s,a) \leftarrow r(s,a) + \mathbb{E}_{a' \sim \pi_{new}}[Q(s',a')]

We can do:

Q(s,a) \leftarrow r(s,a) + V(s')

But how do we fit this $V’$ function?

$V \leftarrow \argmin_{V} \frac{1}{N} \sum_{i=1}^N l(V(s_i), Q(s_i, a_i))$
1. MSE Loss $(V(s_i) - Q(s_i, a_i))^2$
  1. Problem is ⇒ the actions come from the exploration policy $\pi_\beta$ not from $\pi_{new}$
  1. Gives us $\mathbb{E}_{a \sim \pi_\beta}[Q(s,a)]$

Think about this:

We’ve probably seen only a bit or none of action in the “exact” same state
1. But there might be very “similar” states that we execute action on ⇒ There’s not bins of states but distributions of states
1. Can we use those “similar states” as extra data points for us to perform generalization on?
1. But what if we use a “quantile” / “expectile” ⇒ expectile is like a quantile squared
  1. Upper expectile / quantile is the best policy supported by the data

Implicit Q-Learning

Expectile:

l_2^\tau (x) = \begin{cases} (1-\tau)x^2 &\text{if } x>0 \\ \tau x^2 &\text{otherwise} \end{cases}

Intuition:

MSE penalizes positive and negative errors equally

expectile penalizes positive and negative with different weights depending on $\tau \in [0,1]$

Weights given to positive and negative erros in expectile regression. Taken from IQL paper

Formally, it could be shown that if we use

V \leftarrow \argmin_{V} \mathbb{E}_{(s,a) \sim D} [l_2^\tau(V(s)-Q(s,a))]

In practice, $Q(s,a)$ would be a target network

Formally, we can prove that provided with a big enough $\tau$ ,

V(s) \leftarrow \max_{a \in \Omega(s)} Q(s,a)

Where

\Omega(s) = \{a: \pi_\beta(a|s) \ge \epsilon \}

Kostrikov, Nair, Levine. Offline Reinforcement Learning with Implicit Q-Learning. ‘21

📌

Oh yes, that’s my postdoc’s paper (as the first author)! This is absolutely an amazing paper and he is absolutely an amazing person, also this is one of the papers I read for entering into Sergey’s group. I hope you get to check out this paper!

Conservative Q-Learning (CQL)

Kumar, Zhou, Tucker, Levine. Conservative Q-Learning for Offline Reinforcement Learning

Directly repair overestimated actions in the Q function

Intuition: Push down on areas that have errorneous high Q values

We can formally show that $\hat{Q}^\pi \le Q^\pi$ for large enough $\alpha$

But with this objective, we’re pressing down on actually “good” actions as well ⇒ so add additional terms that pushes up on good samples supported by data

No longer guarenteed that $\forall (s,a) \hat{Q}^\pi (s,a) \le Q^\pi(s,a)$

But $\forall s\in D, \mathbb{E}_{\pi(a|s)}[\hat{Q}(s,a)] \le \mathbb{E}_{\pi(a|s)}[Q^\pi(s,a)]$

In practice, we add a regularizer $R(\mu)$ in $L_{CQL}(\hat{Q}^\pi)$ so that the $\mu$ doesn’t need to be calculated directly.

L_{CQL}(\hat{Q}^\pi) = \max_{\mu} \{ \alpha\mathbb{E}_{s\sim D, a\sim \mu(a|s)}[\hat{Q}^\pi(s,a)] - \alpha \mathbb{E}_{(s,a) \sim D}[Q(s,a)] \} + \mathbb{E}_{(s,a,s') \sim D}[Q(s,a) - (r(s,a)+\mathbb{E}[Q(s',a')]))^2]

Common choice: $R(\mu) = \mathbb{E}_{s \sim D} [H(\mu(\cdot | s))]$

⇒ Then $\mu(a|s) \propto \exp[Q(s,a)]$ ⇒ $\mathbb{E}_{a \sim \mu(a|s)}[Q(s,a)] = \log \sum_a \exp(Q(s,a))$

For discrete actions, we can just calculate this $\log \sum_a \exp(Q(s,a))$ directly

For continuous actions, use importance sampling to estimate $\mathbb{E}_{a \sim \mu (a|s)} [Q(s,a)]$

Model-based Offline RL

What goes wrong when we cannot collect more data?

MOPO: Model-Based Offline Policy Optimization

Yu*, Thomas*, Yu, Ermon, Zou, Levine, Finn, Ma. MOPO: Model-Based Offline Policy Optimization. ‘20 MOReL : Model-Based Offline Reinforcement Learning. ’20 (concurrent)

“punish” the policy for exploiting

\tilde{r}(s,a) = r(s,a) -\lambda u(s,a)

where $u(s,a)$ is model uncertainty about the state and action

$u$ need to at least as large as the error in the model (according to some kind of divergence) ⇒ still an open problem to get a good estimate

“Use ensemble as an error proxy for the uncertainty metric” ⇒ current method

Theoretical analysis:

In particular, $\forall \delta \ge \delta_{\min}$

Some implications:

\eta_M(\hat{\pi}) \ge \eta_M(\pi^{B})-2\lambda \epsilon_u(\pi^{B})

We can do almost always better then the behavior(exploration) policy (since $\delta$ is very small for $\pi^B$ )

\eta_M(\hat{\pi}) \ge \eta_M(\pi^*)-2\lambda \epsilon_u(\pi^*)

Quantifies the optimality “gap” in terms of model error

COMBO: Convervative Model-based RL

Yu, Kumar, Rafailov, Rajeswaran, Levine, Finn. COMBO: Conservative Offline Model-Based Policy Optimization. 2021.

📌

Basic idea: just like CQL minimizes Q-value of policy actions, we can minimize Q-value of model state-action tuples

Intuition: if the model produces something that looks clearly different from real data, it’s easy for the Q-function to make it look bad

Trajectory Transformer

Janner, Li, Levine. Reinforcement Learning as One Big Sequence Modeling Problem. 2021.

Model drew with Auto-regressive sequence model

Train a joint state-action model
1. $p_\beta(\tau) = p_\beta(s_1,a_2, \dots, s_T, a_T)$
1. Intuitively we want to optimize for a plan for a sequence of actions that has a high probability under the data distribution

Use a big expressive model (Transformer)
1. Subscript in the model image just shows the “timestep, dimension” of state and action spaces
1. Diagram is an Auto-regressive sequence model (LSTM)
1. With transformer need a causal mask
  1. GPT-style model
1. Because we are regressing on both state and action sequences we can have accurate predictions out to much longer horizons

Control
1. Beam search, but use $\sum_t r(s_t,a_t)$ instead of probability
  1. Given current sequence, sample next tokens from model
  1. Store top $K$ tokens with highest cumulative reward (but as we progress only select high-probability sequences)
1. Other methods like MCTS works as well

This works because

Generating high-probability trajectories avoids OOD states & actions

using a really big model works well in offline mode

Which Offline Algorithm to use?

If only want to train offline
- CQL
  - Just one hyper-param, well understood and widely tested
  - Doesn’t finetune well
- IQL
  - More flexible (offline + online)
  - More hyperparameters

Only train offline and finetune online
- Advantage-weighted actor-critic (AWAC)
  - Widely used an well tested
- IQL
  - Performs much better than AWAC!

If have a good way to train models in the domain
- Not always easy to train a good model in a specific domain!
- COMBO
  - Similar properties as CQL but benefits from models
- Trajectory Transformer
  - Very powerful and effective models
  - Extremely computationally expensive to train and evaluate

Why offline RL

Open Problems

An offline RL workflow
- Supervised learning workflow: train/test split
- Offline RL workflow: Train offline, evaluate online
- Starting Point
  - Kumar, Singh, Tian, Finn, Levine. A Workflow for Offline Model-Free Robotic Reinforcement Learning. CoRL 2021

Statistical guarantees
- Biggest challenge: distributional shift/counterfactuals
- Can we make any guarantees?

Scalable methods, large-scale applications
- Dialogue systems
- Data-driven navigation and driving

RL Theory

📌

Effective analysis is very hard in RL without strong assumptions Trick is to make assumptions that admit interesting conclusions without divorcing us (too much) from reality

What is the point:

Prove that our RL algorithms will work perfectly every time
1. Usually not possible with current deep RL methods, which are often not even guarenteed to converge

Understand how errors are affected by problem parameters
1. Do larger discounts work better than smaller ones?
1. If we want half the eror, do we need 2x the samples, 4x, or something else?
1. Usually we use precise theory to get imprecise qualitative conclusions about how various factors influence the performance of RL algorithms under strong assumptions, and try to make the assumptions reasonable enough that these conclusions are likely to apply to real problems (but they are not guarenteed to apply to real problems)

⚠️

Don’t take someone seriously if they say their RL algorithm has “provable guarantees” the assumptions are always unrealistic, and theory is at best a rough guide to what might happen

Exploration

Performance of RL is greatly complicated by exploration - how likely are we to find potentially sparse rewards?

Theoretical guarantees typically address worst case performance ⇒ but worst case exploration is extremely hard

🧙🏽‍♂️

Goal: Show that exploration method is

Poly(|S|, |A|, 1/(1-\gamma))

If we “abstract away” exploration, how many samples do we need to effectively learn a model or value function that results in good performance?
- “generative model” assumption: assume we can sample from $P(s’|s,a)$ for any $(s,a)$
- “oracle exploration” assumption: For every $(s,a)$ , sample $s’ \sim P(s’|s,a)$ N times

Basic Sample Complexity Analysis

RL Theory Textbook. Agarwal, Jiang, Kakade, Sun.

https://rltheorybook.github.io

“Oracle Exploration”: for every $(s,a)$ , sample $s’ \sim P(s’|s,a)$ N times

Simple “model-based” algorithm

$\hat{P}(s’|s,a) = \frac{\#(s,a,s’)}{N}$
1. Count number of transitions

Given $\pi$ , use $\hat{P}$ to estimate $\hat{Q}^\pi$

We want to measure worst case performance
1. How close is $\hat{Q}^\pi$ to $Q^\pi$ ?
1. How close is $\hat{Q}^*$ (optimal function learned under $\hat{P}$ ) to $Q^*$ (optimal function learned under real $P$ )?
1. How good is the resulting policy?

“How close is $\hat{Q}^\pi$ to $Q^\pi$ ?”

\begin{split} ||Q^\pi(s,a) - \hat{Q}^\pi(s,a)||_\infin &\le \epsilon \\ \max_{s,a} |Q^\pi(s,a) - \hat{Q}(s,a)| &\le \epsilon \end{split}

“How close is $\hat{Q}^*$ to $Q^*$ ?”

||Q^*(s,a) - \hat{Q}^*(s,a)||_\infin \le \epsilon

“How good is the resulting policy?”

||Q^*(s,a) - Q^{\hat{\pi}}(s,a)||_\infin \le \epsilon

Concentration Inequalities

How fast our estimate of random variable converges to the true underlying value (in terms of # of samples)

Hoeffding’s Inequality (For continuous distributions)

Suppose $X_1, \dots, X_n$ are a sequence of independent, identically distributed (i.i.d.) random variables with mean $\mu$ . Let $\bar{X_n} = n^{-1}\sum_{i=1}^n X_i$ . Suppose that $X_i \in [b_{-},b_{+}]$ with probability $1$ , then

\mathbb{P}(\bar{X}_n \ge \mu + \epsilon) \le \exp \{-\frac{2n\epsilon^2}{(b_{+}-b_{-})^2}\}

Therefore if we estimate $\mu$ with $n$ samples the probability we’re off by more than $\epsilon$ is at most $2 \exp \{ \frac{2n\epsilon^2}{(b_{+}-b_{-})^2} \}$ (since we can be off on both sides). So if we want this probability to be $\delta$ :

\begin{split} \delta &\le 2\exp\{-\frac{2n\epsilon^2}{(b_{+}-b_{-})^2}\} \\ \log \frac{\delta}{2} &\le -\frac{2n\epsilon^2}{(b_{+}-b_{-})^2} \\ \epsilon^2 &\le \frac{(b_{+}-b_{-})^2}{2n} \log \frac{2}{\delta} \\ \epsilon &\le \frac{b_{+}-b_{-}}{\sqrt{2n}} \sqrt{\log \frac{2}{\delta}} \end{split}

⚠️

Error

\epsilon

scales as

\frac{1}{\sqrt{n}}

Concentration for Discrete Distributions

Let $z$ be a discrete random variable that takes values in $\{1, 2, \dots, d \}$ , distributed according to $q$ . We can write $q$ as a vector where $\vec{q} = [\mathbb{P}(z=j)]_{j=1}^d$ . Assume we have $N$ iid samples, and that our empiraical state of $\vec{q}$ is $[\hat{q}]_j = \sum_{i=1}^N 1\{z_i=j\} / N$

We have that $\forall \epsilon > 0$ ,

\mathbb{P}(||\hat{\vec{q}}-\vec{q}||_2 \ge \frac{1}{\sqrt{N}} + \epsilon) \le \exp\{-N\epsilon^2\}

Which implies:

\mathbb{P}(||\hat{\vec{q}} - \vec{q}||_1 \ge \sqrt{d}(\frac{1}{\sqrt{N}}+\epsilon)) \le \exp\{-N\epsilon^2\}

Let

\delta = \mathbb{P}(||\hat{\vec{q}} - \vec{q}||_1 \ge \sqrt{d}(\frac{1}{\sqrt{N}}+\epsilon))

Then

\begin{split} \delta &\le \exp\{-N\epsilon^2\} \\ \epsilon &\le \frac{1}{\sqrt{N}} \sqrt{\log \frac{1}{\delta}} \\ N &\le \frac{1}{\epsilon^2} \log \frac{1}{\delta} \end{split}

Using concentration inequalities, we see that in the “Basic Sample Complexity Analysis”, the state transition estimation difference is

\begin{split} ||\hat{P}(s'|s,a) - P(s'|s,a)||_1 &\le \sqrt{|S|} (1/\sqrt{N} + \epsilon) \\ &\le \sqrt{\frac{|S|}{N}} + \sqrt{\frac{|S|\log (1/\delta)}{N}} \\ &\le c\sqrt{\frac{|S|\log (1/\delta)}{N}} \end{split}

Now: Relate error in $\hat{P}$ to error in $\hat{Q}^\pi$

Recall:

\begin{split} Q^\pi(s,a) &= r(s,a) + \gamma \mathbb{E}_{s' \sim \mathbb{P}(s'|s,a)}[V^\pi(s')] \\ Q^\pi(s,a) &= r(s,a) + \gamma\sum_{s'} \mathbb{P}(s'|s,a) V^\pi(s') \end{split}

So if we write out the transition fuction $P$ , the Q function $Q^\pi$ , reward function $r$ , and value function $V^\pi$ as matrices:

Q^\pi = r + \gamma PV^\pi

Remember that $V$ function is just an expectation over the $Q$ function (a sum) ⇒ so we can also write it as an expectation (where $\Pi \in \mathbb{R}^{|S| \times (|S||A|)}$ and is a probability matrix)

V^\pi = \Pi Q^\pi

With this, (and $P^\pi = P \Pi$ )

Q^\pi = r + \gamma P^\pi Q^\pi

\begin{split} (I - \gamma P^\pi)Q^\pi &= r \\ Q^\pi &= (I-\gamma P^\pi)^{-1} r \end{split}

And turns out the matrix $(I - \gamma P^\pi)$ is always gonna be invertible

Simulation Lemma:

Q^\pi - \hat{Q}^\pi = \gamma \overbrace{(I-\gamma \hat{P}^\pi)^{-1}}^{\mathclap{\text{Evaluation Operator: Turns reward function into Q function}}} \underbrace{(P-\hat{P})}_{\mathclap{\text{Difference in model probability}}} V^\pi

Proof:

\begin{split} Q^\pi - \hat{Q}^\pi &= Q^\pi - (I-\gamma \hat{P}^\pi)^{-1}r \\ &=(I-\gamma\hat{P}^\pi)^{-1}(I - \gamma \hat{P}^\pi)Q^\pi - (I-\gamma \hat{P}^\pi)^{-1} r \\ &=(I-\gamma\hat{P}^\pi)^{-1}(I - \gamma \hat{P}^\pi)Q^\pi - (I-\gamma \hat{P}^\pi)^{-1} (I-\gamma P^\pi) Q^\pi \\ &=(I-\gamma\hat{P}^\pi)^{-1} [(I-\gamma \hat{P}^\pi) - (I-\gamma P^\pi)] Q^\pi \\ &=\gamma(I-\gamma\hat{P}^\pi)^{-1} (P^\pi - \hat{P}^\pi)Q^\pi \\ &=\gamma(I-\gamma\hat{P}^\pi)^{-1} (P \Pi - \hat{P} \Pi)Q^\pi \\ &=\gamma(I-\gamma\hat{P}^\pi)^{-1} (P - \hat{P})\Pi Q^\pi \\ &=\gamma(I-\gamma\hat{P}^\pi)^{-1} (P- \hat{P})V^\pi \\ \end{split}

Another Lemma:

Given $P^\pi$ and any vector $\vec{v} \in \mathbb{R}^{|S||A|}$ , we have

||(I-\gamma P^\pi)^{-1}\vec{v}||_\infin \le \frac{||\vec{v}||_\infin}{1-\gamma}

“Q function” corresponding to “reward” $\vec{v}$ is at most $(1-\gamma)^{-1}$ times larger

Where does this $(1-\gamma)^{-1}$ come from? Geometric series of $\sum_{t=0}^\infin \gamma^t c = \frac{c}{1-\gamma}$

Let

\vec{w} = (I\gamma P^\pi)^{-1}\vec{v}

Then

\begin{split} ||\vec{v}||_\infin &= ||(I-\gamma P^\pi)\vec{w}||_\infin \\ &\overbrace{\ge}^{\mathclap{\text{Triangular Inequality}}} ||\vec{w}||_\infin - \gamma ||P^\pi \vec{w}||_\infin \\ &\ge ||\vec{w}||_\infin - \gamma||\vec{w}||_\infin \\ &\ge (1-\gamma) ||\vec{w}||_\infin \end{split}

Putting the lemmas together,

\begin{split} ||(I-\gamma P^\pi)^{-1}\vec{v}||_\infin &\le ||\vec{v}||_\infin \\ \end{split}

Let the special case $\vec{v} = \gamma(P-\hat{P})V^\pi$

\begin{split} Q^\pi - \hat{Q}^\pi &= \gamma (I-\gamma \hat{P}^\pi)^{-1}(P-\hat{P})V^\pi \\ ||Q^\pi - \hat{Q}^\pi||_\infin &= ||\gamma(I-\gamma \hat{P}^\pi)^{-1}(P-\hat{P})V^\pi||_\infin \\ &\le \frac{\gamma}{1-\gamma} ||(P-\hat{P})V^\pi||_\infin \\ &\le \frac{\gamma}{1-\gamma}(\max_{s,a} ||P(\cdot |s,a) - \hat{P}(\cdot|s,a)||_1) ||V^\pi||_\infin \end{split}

We can bound $||V^\pi||_\infin$

\sum_{t=0}^\infin \gamma^t r_t \le \frac{1}{1-\gamma}R_{max}

With this bound,

||Q^\pi-\hat{Q}^\pi||_\infin \le \frac{\gamma}{(1-\gamma)^2} R_{max} (\max_{s,a} ||P(\cdot |s,a) - \hat{P}(\cdot|s,a)||_1)

With the previous bound on

\begin{split} ||P(\cdot|,s,a) - \hat{P}(\cdot|s,a)||_1 &\le \sqrt{\frac{|S|}{N}} + \sqrt{\frac{|S|\log (1/\delta)}{N}} \\ &\le c\sqrt{\frac{|S|\log (1/\delta)}{N}} \end{split}

We conclude:

||Q^\pi-\hat{Q}^\pi||_\infin \le \epsilon = \frac{\gamma}{(1-\gamma)^2} R_{max} c_2 \sqrt{\frac{|S| \log(\delta^{-1})}{N}}

⚠️

Error grows quadratically in the horizon

(1-\gamma)^{-2}

, each backup accumulates error

What about $||Q^* - \hat{Q}^*||_\infin$ ?

Supremium - lower upper bound of a function (greatest value of a function), one useful identity

|\sup_x f(x) - \sup_x g(x)| \le \sup_x |f(x)-g(x)|

And

||Q^*-\hat{Q}^*||_\infin = ||\sup_\pi Q^\pi - \sup_\pi \hat{Q}^\pi||_\infin \le \sup_\pi ||Q^\pi - \hat{Q}^\pi||_\infin \le \epsilon

What about $||Q^* - Q^{\hat{\pi}^*}||_\infin$ ?

\begin{split} ||Q^* - Q^{\hat{\pi}^*}||_\infin &= ||Q^* - \hat{Q}^{\hat{\pi}^*}+\hat{Q}^{\hat{\pi}^*} - Q^{\hat{\pi}^*}||_\infin \\ &\le ||Q^* - \underbrace{\hat{Q}^{\hat{\pi}^*}}_{\hat{Q}^*}||_\infin + ||\underbrace{\hat{Q}^{\hat{\pi}^*} - Q^{\hat{\pi}^*}}_{\mathclap{\text{Same Policy}}}||_\infin \\ &\le 2\epsilon \end{split}

Fixed Q-Iteration

Abstract model of exact Q-iteration

Q_{k+1} \leftarrow TQ_k = r+\gamma P \max_{a} Q_k

Abstract model of approximate fitted Q-iteration:

\hat{Q}_{k+1} \leftarrow \argmin_{\hat{Q}} ||\hat{Q} - \hat{T}\hat{Q}_k||

Where $\hat{T}$ is the approximate bellman operator:

\hat{T}Q = \underbrace{\hat{r}}_{\mathclap{\hat{r}(s,a) = \frac{1}{N(s,a)}\sum_i \delta((s_i,a_i) = (s,a)) r_i}} + \gamma \overbrace{\hat{P}}^{\mathclap{\hat{P}(s'|s,a) = \frac{N(s,a,s')}{N(s,a)}}} \max_a Q

Note: We will not be computing $\hat{P}$ and $\hat{r}$ , it would just be the effect of averaging together transitions in the data (having different gradients for different samples)

We will assume an infinity norm here because there will be no convergnce if using L2 norm

Erorrs come from

$T \ne \hat{T}$
- Sampling Error

$\hat{Q}_{k+1} \ne \hat{T}\hat{Q}_k$
- Approximation Error

Sampling Error:

\begin{split} |\hat{T}Q(s,a) - TQ(s,a)| &= |\hat{r}(s,a)-r(s,a)+\gamma(\mathbb{E}_{\hat{P}}[\max_{a'} Q(s',a')] - \mathbb{E}_{P}[\max_{a'} Q(s',a')])| \\ &\le |\hat{r}(s,a) - r(s,a)| + \gamma {|\mathbb{E}_{\hat{P}}[\max_{a'}Q(s',a')]-\mathbb{E}_{P}[\max_{a'}Q(s',a')]|} \\ \end{split}

Note:

$|\hat{r}(s,a) - r(s,a)|$
- Estimation error of continuous random variable, use Hoeffding’s Inequality!
- $\le 2 R_{max} \sqrt{\frac{\log (\delta^{-1})}{2N}}$

$|\mathbb{E}{\hat{P}}[\max{a'}Q(s',a')]-\mathbb{E}{P}[\max{a'}Q(s',a')]|$
- $= \sum_{s’} (\hat{P}(s’|s,a) - P(s’|s,a)) \max_{a’} Q(s’,a’)$
- $\le \sum_{s’} |\hat{P}(s’|s,a) - P(s’|s,a)| \max_{s’,a’} Q(s’,a’)$
  - $= ||\hat{P}(\cdot|s,a) - P(\cdot|s,a)||_1 ||Q||_\infin$
- $\le c||Q||_\infin \sqrt{\frac{\log(\delta^{-1})}{N}}$

|\hat{T}Q(s,a) -TQ(s,a)| \le 2R_{max} \sqrt{\frac{\log(\delta^{-1})}{2N}} + c||Q||_\infin \sqrt{\frac{\log(\delta^{-1})}{N}}

And

||\hat{T}Q - TQ||_\infin \le 2R_{max} c_1 \sqrt{\frac{\log(\frac{|S||A|}{\delta})}{2N}} + c_2||Q||_\infin \sqrt{\frac{\log(\frac{|S|}{\delta})}{N}}

Approximation Error:

Assume error: $||\hat{Q}_{k+1} - T\hat{Q}_k||_\infin||_\infin \le \epsilon_k$

This is a strong assumption!

\begin{split} ||\hat{Q}_k - Q^*||_\infin &= ||\hat{Q}_k - T\hat{Q}_{k-1} + T\hat{Q}_{k-1}-Q^*||_\infin \\ &= ||(\hat{Q}_k - T\hat{Q}_{k-1}) + (T\hat{Q}_{k-1} - \underbrace{TQ^*}_{\mathclap{\text{Using the fact that $Q^*$ is a fixed point of $T$}}})||_\infin \\ &\le ||\hat{Q}_k - T\hat{Q}_{k-1}||_\infin + ||T\hat{Q}_{k-1} - TQ^*||_\infin \\ &\le \epsilon _{k-1} + \underbrace{\gamma ||\hat{Q}_{k-1}- Q^*||_\infin}_{\mathclap{\text{Using the fact that $T$ is a $\gamma$-contraction}}} \\ \text{Unroll the recursion,} \\ &\le \sum_{i=0}^{k-1} \gamma^i \epsilon_{k-i-1} + \gamma ||\hat{Q}_{k-1} - Q^*||_\infin \\ \end{split}

\lim_{k \to \infin} ||\hat{Q}_k - Q^*||_\infin \le \sum_{i=0}^{\infin} \gamma^i \max_{k} \epsilon_k = \frac{1}{1-\gamma}||\epsilon||_\infin

Putting it together:

\begin{split} ||\hat{Q}_k - T\hat{Q}_{k-1}||_\infin &= ||\hat{Q}_k - \hat{T}\hat{Q}_{k-1} + \hat{T}\hat{Q}_{k-1} - T\hat{Q}_{k-1}||_\infin \\ &\le \underbrace{||\hat{Q}_k - \hat{T}\hat{Q}_{k-1}||_\infin}_{\mathclap{\text{Approximation Error}}} + \underbrace{||\hat{T}\hat{Q}_{k-1} - T\hat{Q}_{k-1}||_\infin}_{\mathclap{\text{Sampling Error}}} \\ \end{split}

Note:

From previous proofs, $\text{Sampling Error}, \text{Approx Error} \in O((1-\gamma)^{-1})$

More advanced results can be derived with $p$ -norms under some distribution

Variational Inference

No RL content in this chapter, but heavy links to RL algorithms

Latent Variable Model

We have data points $x$ , we want to model a distribution of $x$ with the help of latent variable $z$ .

How do we train latent variable models?

Model $p_\theta(\vec{x})$

Data: $D = \{ x_1, x_2, x_3, \dots, x_N \}$

MLE fit: $\theta \leftarrow \argmax_{\theta} \frac{1}{N} \sum_i \log p_\theta(x_i)$
- $p(x) = \int p(x|z) p(z) dz$
- $\theta \leftarrow \argmax_\theta \frac{1}{N} \sum_i \log (\underbrace{\int p_\theta(x_i|z)p(z)dz}_{\text{completely untractable}})$

Estimating the log-likelihood

🧙🏽‍♂️

Use Expected Log-likelihood

\theta \leftarrow \argmax_\theta \frac{1}{N} \sum_i \mathbb{E}_{z \sim p(z|x_i)}[\log p_\theta(x_i,z)]

Intuition:

Guess most likely $z$ given $x_i$ , and pretend it is the right one
- But there are many possible values of $z$ so use the distribution $p(z|x_i)$

But how do we calculate $p(z|x_i)$ ?
- Approximate with $q_i(z) = N(\mu_i, \sigma_i)$
  - Note that with each data point $x_i$ , they all have different $q_i$
  - With any $q_i(z)$ , we can construct a lower bound on $\log p(x_i)$
  - Maximize this bound (assume this bound is tight), we can push up on $\log p(x_i)$

\begin{split} \log p(x_i) &= \log \int_z p(x_i|z) p(z) \\ &= \log \int_z p(x_i|z)p(z)\frac{q_i(z)}{q_i(z)} \\ &=\log \mathbb{E}_{z \sim q_i(z)} [\frac{p(x_i|z)p(z)}{q_i(z)}] \end{split}

Note:

Yensen’s Inequality (For concave function)

\log \mathbb{E}[y] \ge \mathbb{E}[\log y]

\begin{split} \log p(x_i) &=\log \mathbb{E}_{z \sim q_i(z)} [\frac{p(x_i|z)p(z)}{q_i(z)}] \\ &\ge \mathbb{E}_{z \sim q_i(z)} [\log \frac{p(x_i|z)p(z)}{q_i(z)}] \\ &\quad = \mathbb{E}_{z \sim q_i(z)}[\log p(x_i|z) + \log p(z)] - \mathbb{E}_{z \sim q_i(z)} [\log q_i(z)] \\ &\quad = \mathbb{E}_{z \sim q_i(z)}[\log p(x_i|z) + \log p(z)] + H(q_i) \end{split}

Note about entropy:

H(p) = -\mathbb{E}_{x \sim p(x)}[\log p(x)] = -\int_x p(x)\log p(x) dx

Intuitions:

How random is the random variable?

How large is the log probability in expectation under itself?

Also note about KL-Divergence:

D_{KL}(q ||p) = \mathbb{E}_{x \sim q(x)}[log \frac{q(x)}{p(x)}] = \mathbb{E}_{x \sim q(x)} [\log q(x)] - \mathbb{E}_{x \sim q(x)}[\log p(x)] = -\mathbb{E}_{x \sim q(x)}[\log p(x)] - H(q)

Intuitions:

How different are two distributions?

How small is the expected log probability of one distribution under another, minus entropy?

So the variational approximation

\begin{split} \log p(x_i) &\ge \overbrace{\mathbb{E}_{z \sim q_i(z)}[\log p(x_i|z) + \log p(z)] + H(q_i)}^{L_i(p,q_i)} \\ \end{split}

So what makes a good $q_i(z)$ ?

$q_i(z)$ should approximate $p(z|x_i)$
- Compare in terms of KL-divergence $D_{KL}(q_i(z) || p(z|x))$

Why?

\begin{split} D_{KL}(q_i(z) || p(z|x_i)) &= \mathbb{E}_{z \sim q_i(z)}[\log \frac{q_i(z)}{p(z|x_i)}] = \mathbb{E}_{z \sim q_i(z)}[\log \frac{q_i(z) p(x_i)}{p(x_i,z)}] \\ &= - \mathbb{E}_{z \sim q_i(z)}[\log p(x_i|z)] + \log p(z)] + \mathbb{E}_{z \sim q_i(z)}[\log q_i(z)] + \mathbb{E}_{z \sim q_i(z)}[\log p(x_i)] \\ &= - \mathbb{E}_{z \sim q_i(z)}[\log p(x_i|z)] + \log p(z)] - H(q_i) + \mathbb{E}_{z \sim q_i(z)}[\log p(x_i)] \\ &=- L_i(p,q_i) + \log p(x_i) \end{split}

Also:

\log p(x_i) = D_{KL}(q_i(x_i)||p(z|x_i)) + L_i(p,q_i)

In fact minimizing the KL-divergence has the effect of tightening then bound!

But how to improve $q_i$ ?

We can let $q_i = N(\mu_i, \sigma_i)$ and use gradient $\nabla_{\mu_i} L_i(p,q_i)$ and $\nabla_{\sigma_i} L_i(p,q_i)$
- But too many parameters! We have $|\theta| + (|\mu_i|+|\sigma_i|) \times N$ parameters

Then can we use
- $q_i(z) = q_\phi(z|x_i) \approx p(z|x_i)$ ?
- Amortized Variational Inference!

Amortized Variational Inference

L_i = \underbrace{\mathbb{E}_{z \sim q_\phi(z|x_i)}[\log p_\theta(x_i|z) + \log p(z)]}_{J(\phi) = \mathbb{E}_{z \sim q_\phi(z|x_i)}[r(x_i,z)]} + H(q_\phi(z|x_i))

We can directly calculate the derivative for the entropy term but the first term $J(\phi)$ seems a bit problematic.

But this format looks a lot like policy gradient!

\nabla J(\phi) \approx \frac{1}{M} \sum_j \nabla_\phi \log q_\phi(z_j|x_i) r(x_i,z_j)

What’s wrong with this gradient?

Perfectly viable approach, but not best approach

Tends to suffer from high variance

The reparameterization trick

⚠️

In RL we cannot use this trick because we cannot calculate gradient through the transition dynamics, but with variational inference we can

q_\phi(z|x) = N(\mu_\phi(x), \sigma_\phi(x)) \\ z = \mu_\phi(x) + \epsilon \sigma_\phi(x), \epsilon \sim N(0,1)

This makes $z$ an independent function of a random variable $\epsilon$ that is independent of $\phi$

So now:

\begin{split} J(\phi) &= \mathbb{E}_{z \sim q_\phi(z|x_i)}[r(x_i,z)] \\ &=\mathbb{E}_{\epsilon \sim N(0,1)}[r(x_i,\mu_\phi(x_i)+\epsilon \sigma_\phi(x_i))] \end{split}

And now to estimate $\nabla_{\phi} J(\phi)$

sample $\epsilon_1, \dots, \epsilon_M$ from $N(0,1)$ (even a single sample works well)
- $\epsilon$ treated as a constant when computing gradient

$\nabla_\phi J(\phi) \approx \frac{1}{M} \sum_j \nabla_\phi r(x_i, \mu_\phi(x_i) + \epsilon_j \sigma_\phi(x_i))$

This is useful because now we are using the derivative of the $r$ function

Another Perspective of $L_i$

\begin{split} L_i &= \mathbb{E}_{z \sim q_\phi(z|x_i)}[\log p_\theta(x_i|z) + \log p(z)] + H(q_\phi(z|x_i)) \\ &=\mathbb{E}_{z \sim q_\phi(z|x_i)}[\log p_\theta(x_i|z)] + \underbrace{\mathbb{E}_{z \sim q_\phi(z|x_i)}[\log p(z)] + H(q_\phi(z|x_i))}_{-D_{KL}(q_\phi(z|x_i)||p(z))} \\ &= \mathbb{E}_{z \sim q_\phi(z|x_i)}[\log p_\theta(x_i|z)]-D_{KL}(q_\phi(z|x_i)||p(z)) \\ &=\mathbb{E}_{\epsilon \sim N(0,1)}[\log p_\theta(x_i|\mu_\phi(x_i) + \epsilon \sigma_\phi(x_i))]-D_{KL}(q_\phi(z|x_i)||p(z)) \\ &\approx \log p_\theta(x_i | \mu_\phi(x_i) + \epsilon \sigma_\phi (x_i))-D_{KL}(q_\phi(z|x_i)||p(z)) \\ \end{split}

Reparameterization trick vs. Policy Gradient

Policy Gradient
- Can handle both discrete and continuous latent variables
- High variance, requires multiple samples & small learning rates

Reparameterization Trick
- Only continuous latent variables
- Simple to implement & Low variance

Example Models

VAE Variational Autoencoder

\max_{\theta, \phi} \frac{1}{N} \sum_i \log p_\theta(x_i|\mu_\phi(x_i) + \epsilon \sigma_\phi(x_i)) - D_{KL}(q_\phi(z|x_i)||p(z))

Conditional Models

Generates $y$ given $x, z$

L_i = \mathbb{E}_{z \sim q_\phi(z|x_i, y_i)}[\log p_\theta(y_i|x_i,z) + \log p(z|x_i)]+H(q_\phi(z|x_i,y_i))

General Introduction to RL (LEC 1)

Fundamental Theorem of RL(Lec 4)

Notations + Markov Property

Definition of Markov Chain

Definition of Markov Decision Process

Partially Observed Markov Decision Process

Goal of RL (Finite Horizon / Episodic)

Goal of RL (Infinite Horizon)

Expectations and Stochastic Systems

High-level anatomy of reinforcement learning algorithms

Value Function & Q Function

Q-Function Definition

Value Function Definition

Bellman Operator

Information Theory (LEC 14)

Optimal Control and Planning Algorithms

Open-loop Planning

Stochastic Optimization

Close-loop Planning

Monte-Carlo Tree Search (MCTS)

Shootting Methods vs. Collocation

Trajectory Optimization

Linear Case: Linear Quadratic Regularizer (LQR)

LQR for Stochastic and Nonlinear Systems

Additional Reading

Types of RL Algorithms

Supervised Learning of Behaviors(LEC 2)

Imitation Learning

DAgger (Data Aggregation)

Analysis of Imitation Learning

Another way to imitate (Goal Conditional Behavioral Cloning)

Model-Based RL

Value function based algorithms

Direct Policy Gradients

Actor-critic

Tradeoff between algorithms

Sample efficiency

Stability & Ease of use

Different assumptions

Model-Free Alogorithms

Policy Gradients

”REINFORCE algorithm”

Partial Observability

What’s wrong?

How we can modify policy gradient to reduce variance?

With discount factors

Baselines

Off-policy setting

Policy Gradient with Automatic Differentiation

A few reminders about tuning hyper-parameters

Covariant/natural policy gradient

Advanced Policy Gradients

Why does policy gradient work?

Bounding the distribution change (deterministic)

Bounding the distribution change (arbitrary)

Bounding the objective value

Policy Gradients with Constraints

Natural Gradient

Actor-Critic Method

Fitting Q/Value/Advantage Functions

Policy Evaluation

Expectation of rewards

Batch actor-critic algorithm

Discount Factor

Online Actor-critic Algorithm

Off-policy Actor-critic algorithms

Critics as state-dependent baselines

Eligibility traces & n-step returns

Generalized advantage estimation

Examples of actor-critic algorithms

Suggested Readings

Value Function / Q Function Fitting (Value-Based)

Policy Iteration (Fitted Value Iteration)

Policy Iteration without transition probability (Fitted Q-Iteration)

Special Cases of Fixed Q-Fitting

Value Function Learning Theory

Correlation Problem in Q-Learning

Classic Deep Q-Learning Algorithm (DQN)

A general view of Q-Learning

Overestimation in Q-Learning and Double Q-Learning

Optimistic exploration $Reg(T) \in O(\log T)$

Another Perspective of $L_i$